Approximation by Moderately Exponential Algorithms
Paschos, Vangelis (2010), Approximation by Moderately Exponential Algorithms, in Mahjoub, Ali Ridha, Combinatorial Optimization ISCO2010. Recent Progress, Wiley : London
TypeCommunication / Conférence
Conference titleISCO International Symposium on Combinatorial Optimization
Book titleCombinatorial Optimization ISCO2010. Recent Progress
Book authorMahjoub, Ali Ridha
Number of pages416
MetadataShow full item record
Abstract (EN)We present a trade-off between polynomial approximation and exact computation. We show how using ideas from both fields one can design approximation algorithms for several 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 then show how such ratios can be achieved for maximum independent set, minimum vertex cover and minimum set cover.
Subjects / KeywordsApproximation algorithms; Exponential algorithms
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é