| Popis: |
Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and we know that there is not any mathematical formulation that approximates it better than . In other words, it is known that it is hard to approximate to within any constant factor better than , while a -approximation for it can be trivially obtained. In this paper, by a combination of a well-known semidefinite programming formulation and a rounding procedure, along with satisfying new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of on arbitrary graphs, en route answering an open question about the unique games conjecture. |
