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
TypeArticle accepté pour publication ou publié
Journal nameTheoretical Computer Science
MetadataShow full item record
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 / KeywordsExponential algorithms; Approximation algorithms; Min set cover
Showing items related by title and author.
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é