2013 | OriginalPaper | Buchkapitel
New Approximation Algorithms for the Vertex Cover Problem
verfasst von : Franc̨ois Delbot, Christian Laforest, Raksmey Phan
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The vertex cover is a classical NP-complete problem that has received great attention these last decades. A conjecture states that there is no
c
-approximation polynomial algorithm for it with
c
a
constant
strictly less than 2. In this paper we propose a new algorithm with approximation ratio strictly less than 2 (but non constant). Moreover we show that our algorithm has the potential to return
any
optimal solution.