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

Voir/Ouvrir
Type
Article accepté pour publication ou publié
Date
2011
Nom de la revue
Discrete Applied Mathematics
Volume
159
Numéro
17
Éditeur
Elsevier
Pages
1954-1970
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis
Résumé (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.
Mots-clés
Approximation algorithms; Exponential time algorithms; Maximum independent set; Minimum vertex cover