2024/02/22 by Majid Zohrehbandian, Zohrehbandian, Majid
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2403.19680
openalex publication_date 2024/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The vertex cover problem is a famous combinatorial problem, and its complexity has been heavily studied. While a 2-approximation can be trivially obtained for it, 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.