We are given an undirected graph G = (V, E) and an integer 1 k |V | as input. For any node vV, let N[v]={v}{uV :(u,v)E} be the closed neighborhood of v. We have to

find a subset of nodes S V of size |S| k that maximizes vS N[v]. Design a greedy approximation algorithm for this problem that runs in polynomial time, and derive a lower bound on its approximation ratio. Try to ensure that the derived lower bound on the approximation ratio is as large as possible.