
Efficient approximation by “low-complexity” exponential algorithms
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2008), Efficient approximation by “low-complexity” exponential algorithms. https://basepub.dauphine.fr/handle/123456789/6009
View/ Open
Type
Document de travail / Working paperDate
2008Publisher
Université Paris-Dauphine
Series title
Cahiers du LAMSADEPublished in
Paris
Pages
26
Metadata
Show full item recordAuthor(s)
Paschos, VangelisLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Bourgeois, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
This paper proposes a way to bring together two seemingly “foreign” domains that are the polynomial approximation and the exact computation for NP-hard problems. We show how one can match ideas from both areas in order to design approximation algorithms achieving ratios unachievable 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 then apply these ideas to two famous combinatorial optimization problems, namely, the max independent set and the min vertex cover, as well as to some other problems mainly linked to max independent set by simple approximation preserving reductions.Subjects / Keywords
polynomial approximation; NP-hard problems; min vertex cover; max independent setRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Communication / Conférence
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Boria, Nicolas; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2013) Article accepté pour publication ou publié