Stochastic Minimum Vertex Cover in General Graphs: a $3/2$-Approximation

Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab

Our main result is designing an algorithm that returns a vertex cover of ${\mathcal{G}}^{\star }$ with size at most $(3/2+\epsilon )$ times the expected size of the minimum vertex cover, using…