The approximability behavior of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
Demange, Marc; Paschos, Vangelis (1997), The approximability behavior of some combinatorial problems with respect to the approximability of a class of maximum independent set problems, Computational Optimization and Applications, 7, 3, p. 307-324. http://dx.doi.org/10.1023/A:1008660812834
Type
Article accepté pour publication ou publiéExternal document link
http://www.lamsade.dauphine.fr/FILES/publi168.pdfDate
1997Journal name
Computational Optimization and ApplicationsVolume
7Number
3Publisher
Springer
Pages
307-324
Publication identifier
Metadata
Show full item recordAbstract (EN)
We prove that the existence of a polynomial timergr-approximation algorithm (wherergr < 1 is a fixed constant)for a class of independent set problems, leads to a polynomial timeapproximation algorithm with approximation ratio strictly smallerthan 2 for vertex covering, while the non-existence of such analgorithm induces a lower bound on the ratio of every polynomialtime approximation algorithm for vertex covering. We also prove asimilar result for a (maximization) convex programming problemincluding quadratic programming as subproblem.Subjects / Keywords
NP-complete problem; quadratic programming; independent set; vertex covering; polynomial time approximation algorithmRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Demange, Marc (1997) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (1996) Communication / Conférence
-
Demange, Marc; Paschos, Vangelis (1999) Document de travail / Working paper
-
Demange, Marc; Paschos, Vangelis (1995) Communication / Conférence
-
Demange, Marc; Paschos, Vangelis (1997) Article accepté pour publication ou publié