Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011), Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Discrete Applied Mathematics, 159, 17, p. 1954-1970. http://dx.doi.org/10.1016/j.dam.2011.07.009
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
Abstract (EN)Using ideas and results from polynomial time approximation and exact computation we design approximationalgorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, maxindependentset and minvertexcover.
Subjects / KeywordsApproximation algorithms; Exponential time algorithms; Maximum independent set; Minimum vertex cover
Showing items related by title and author.