# Determine the approximation factor for greedy vertex cover algorithm

The approximation factor can be $$Omega(log n)$$.

Consider a bipartite graph $$G$$ with a set $$S_L$$ with $$n$$ nodes on the left side. Also consider a collection of sets $$S_{R,1},S_{R,2},dots,S_{R,n}$$ on the right side where each set $$S_{R,i}$$ has an edge to $$i$$ vertices in $$S_{L}$$ and no two vertices in $$S_{R,i}$$s have common edge . So $$lfloor{frac{n}{i}}rfloor$$ in it. So the sum of size of $$S_{R,i}$$s
$$sum_{i=0}^n |S_{R,i}|=Theta(nlog n).$$

After running GreedyVertexCover on this instance, it select all nodes on right side, but the optimal solution was to select all nodes in $$S_L$$.

Consequently, $$frac{ALG(G)}{OPT(G)}=frac{nlog n}{n}=log n.$$
So the approximation factor of your algorithm is $$Omega(log n)$$.