• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
cahierLamsade271.pdf (462.9Kb)
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
http://dx.doi.org/10.1007/978-3-642-03367-4_44
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

Related items

Showing items related by title and author.

  • Thumbnail
    Efficient approximation of MIN SET COVER by moderately exponential algorithms 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of MIN COLORING by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Article accepté pour publication ou publié
  • Thumbnail
    Efficient approximation by “low-complexity” exponential algorithms 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2008) Document de travail / Working paper
  • Thumbnail
    Exponential approximation schemata for some network design problems 
    Boria, Nicolas; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2013) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo