Thumbnail

Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms

Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009), Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms, in Dehne, Frank; Gavrilova, Marina; Sack, Jörg-Rüdiger; Toth, Csaba D., Algorithms and Data Structures 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings, Springer : Berlin, p. 507-518. http://dx.doi.org/10.1007/978-3-642-03367-4_44

View/Open
Type
Communication / Conférence
Date
2009
Conference title
11th International Symposium on Algorithms and Data Structures (WADS'09)
Conference date
2009-08
Conference city
Banff
Conference country
Canada
Book title
Algorithms and Data Structures 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings
Book author
Dehne, Frank; Gavrilova, Marina; Sack, Jörg-Rüdiger; Toth, Csaba D.
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
5664
Published in
Berlin
ISBN
978-3-642-03366-7
Number of pages
580
Pages
507-518
Publication identifier
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis
Abstract (EN)
We design approximation algorithms 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 max independent set, min vertex cover and min set cover and then extend our results to max clique, max bipartite subgraph and max set packing.
Subjects / Keywords
Complexity; NP-hard; Approximation algorithms