Vertex Cover Instance:An undirected graph G(V,E). Find the smallest C V that intersects all edges. ·NP-hard In(n)-approximation by greedy set cover 2-approximation algorithm: Find a maximal matching; return the matched vertices; .[Khot,Regev 2008]Assuming the unique games conjecture, there is no poly-time(2-e)-approximation algorithm.• NP-hard • -approximation by greedy set cover • 2-approximation algorithm: • [Khot, Regev 2008] Assuming the unique games conjecture, there is no poly-time -approximation algorithm. ln(n) (2 − ϵ) Vertex Cover Instance: An undirected graph . Find the smallest that intersects all edges. G(V, E) C ⊆ V Find a maximal matching; return the matched vertices;