Key points are not available for this paper at this time.
The vertex cover problem is a famous combinatorial problem, and its complexity has been heavily studied. While a 2-approximation for it can be trivially obtained, researchers have not been able to approximate it better than 2-o(1). In this paper, by introducing a new semidefinite programming formulation that satisfies new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route to answering an open question about the correctness of the unique games conjecture.
Majid Zohrehbandian (Thu,) studied this question.