2009/10/01 by George Karakostas · 156 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Cover (algebra) #Discrete mathematics #Graph #Mathematics #Maximum cut #Optimization and Search Problems #Relaxation (psychology) #Set (abstract data type) #Set cover problem #Vertex (graph theory) #Vertex cover
paper · doi:10.1145/1597036.1597045
published in ACM Transactions on Algorithms 5(4), 1-8 (Association for Computing Machinery)
openalex publication_date 2009/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/07
We reduce the approximation factor for the vertex cover to 2 − Θ (1/√log n ) (instead of the previous 2 − Θ ln ln n /2ln n obtained by Bar-Yehuda and Even [1985] and Monien and Speckenmeyer [1985]). The improvement of the vanishing factor comes as an application of the recent results of Arora et al. [2004] that improved the approximation factor of the sparsest cut and balanced cut problems. In particular, we use the existence of two big and well-separated sets of nodes in the solution of the semidefinite relaxation for balanced cut, proven by Arora et al. [2004]. We observe that a solution of the semidefinite relaxation for vertex cover, when strengthened with the triangle inequalities, can be transformed into a solution of a balanced cut problem, and therefore the existence of big well-separated sets in the sense of Arora et al. [2004] translates into the existence of a big independent set.