Thumbnail

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

View/Open
Type
Article accepté pour publication ou publié
Date
2011
Journal name
Discrete Applied Mathematics
Volume
159
Number
17
Publisher
Elsevier
Pages
1954-1970
Publication identifier
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis
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 / Keywords
Approximation algorithms; Exponential time algorithms; Maximum independent set; Minimum vertex cover