Constructive-non-constructive approximation and maximum independent set problem
Demange, Marc; Paschos, Vangelis (1996), Constructive-non-constructive approximation and maximum independent set problem, in Deza, Michel M.; Euler, Reinhardt; Manoussakis, Ioannis, Combinatorics and Computer Science 8th Franco-Japanese and 4th Franco-Chinese Conference, Brest, France, July 3-5, 1995 Selected Papers, Springer : Berlin, p. 194-207. http://dx.doi.org/10.1007/3-540-61576-8_83
TypeCommunication / Conférence
Conference title8th Franco-Japanese and 4th Franco-Chinese Conference on Combinatorics and Computer Science (CCS'95)
Book titleCombinatorics and Computer Science 8th Franco-Japanese and 4th Franco-Chinese Conference, Brest, France, July 3-5, 1995 Selected Papers
Book authorDeza, Michel M.; Euler, Reinhardt; Manoussakis, Ioannis
Series titleLecture Notes in Computer Science
Number of pages415
MetadataShow full item record
Abstract (EN)We apply in the case of the maximum independent set, a general thought process consisting in integrating an information on the optimal objective value in its instance. This thought process for the study of the relative hardness between determining solutions of combinatorial optimization problems and computing (approximately or exactly) their optimal values, allows us to define classes of independent set problems the approximability of which is particularly interesting.
Subjects / Keywordsindependent set; polynomial approximation; complexity
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é
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) Article accepté pour publication ou publié