• 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 MIN SET COVER by moderately exponential algorithms

Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009), Efficient approximation of MIN SET COVER by moderately exponential algorithms, Theoretical Computer Science, 410, 21-23, p. 2184-2195. http://dx.doi.org/10.1016/j.tcs.2009.02.007

View/Open
cahierLamsade278.pdf (298.2Kb)
Type
Article accepté pour publication ou publié
Date
2009
Journal name
Theoretical Computer Science
Volume
410
Number
21-23
Publisher
Elsevier
Pages
2184-2195
Publication identifier
http://dx.doi.org/10.1016/j.tcs.2009.02.007
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Escoffier, Bruno
Bourgeois, Nicolas
Abstract (EN)
We study the approximation of min set cover combining ideas and results from polynomial approximation and from exact computation (with non-trivial worst case complexity upper bounds) for NP-hard problems. We design approximation algorithms for min set cover achieving ratios that cannot be achieved in polynomial time (unless problems in NP could be solved by slightly super-polynomial algorithms) with worst-case complexity much lower (though super-polynomial) than those of an exact computation.
Subjects / Keywords
Exponential algorithms; Approximation algorithms; Min set cover

Related items

Showing items related by title and author.

  • 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 of Combinatorial Problems by Moderately Exponential Algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Communication / Conférence
  • Thumbnail
    Efficient approximation by “low-complexity” exponential algorithms 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2008) Document de travail / Working paper
  • Thumbnail
    Fast Algorithms for min independent dominating set 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence
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