Better approximation ratio for the vertex cover problem
Abstract
Type
Type of the conference item
Journal type
peer reviewed
Educational material type
Conference Name
Journal name
Automata, Languages and Programming, Proceedings
Book name
Book series
Book edition
Alternative title / Subtitle
Description
We reduce the approximation factor for Vertex Cover to 2-Theta(1/root log n) (instead of the previous 2- Theta(log log n/log n), obtained by Bar Yehuda and Even [3], and by Monien and Speckenmeyer [11]). The improvement of the vanishing factor comes as an application of the recent results of Arora, Rao, and Vazirani [2] 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 in [2]. 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 [2] translates into the existence of a big independent set.
Description
Keywords
Subject classification
Citation
Link
<Go to ISI>://000230880500084
Language
en
Publishing department/division
Advisor name
Examining committee
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών