The approximability behavior of some combinatorial problems with respect to the approximability of a class of maximum independent set problems

Demange, Marc; Paschos, Vangelis

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.pdf

Date

1997

Journal name

Computational Optimization and Applications

Volume

Number

Publisher

Springer

Pages

307-324

Abstract (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 algorithm