A randomized 1.885903-approximation algorithm for the minimum vertex cover problem
Majid Zohrehbandian · Zenodo (CERN European Organization for Nuclear Research) · 2022
Vertex cover problem is a famous combinatorial problem and its complexity has been heavily studied over the years. It is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, new properties and new techniques are introduced which lead to approximation ratios smaller than 2 on special graphs. Then, by a combination of semidefinite programming and a rounding procedure, along with satisfying the proposed assumptions, we introduce an approximation algorithm with a performance ratio of 1.885903 on arbitrary graphs.