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
TypeArticle accepté pour publication ou publié
External document linkhttp://www.lamsade.dauphine.fr/FILES/publi168.pdf
Journal nameComputational Optimization and Applications
MetadataShow full item record
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 / KeywordsNP-complete problem; quadratic programming; independent set; vertex covering; polynomial time approximation algorithm
Showing items related by title and author.
A generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratios Paschos, Vangelis; Demange, Marc (1997) Article accepté pour publication ou publié