
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
Type
Article accepté pour publication ou publiéDate
2009Journal name
Theoretical Computer ScienceVolume
410Number
21-23Publisher
Elsevier
Pages
2184-2195
Publication identifier
Metadata
Show full item recordAbstract (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 coverRelated items
Showing items related by title and author.
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Communication / Conférence
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2008) Document de travail / Working paper
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence