Thumbnail - Request a copy

Approximation by Moderately Exponential Algorithms

Paschos, Vangelis (2010), Approximation by Moderately Exponential Algorithms, in Mahjoub, Ali Ridha, Combinatorial Optimization ISCO2010. Recent Progress, Wiley : London

Type
Communication / Conférence
Date
2010
Conference title
ISCO International Symposium on Combinatorial Optimization
Conference date
2010-03
Conference city
Hammamet
Conference country
Tunisie
Book title
Combinatorial Optimization ISCO2010. Recent Progress
Book author
Mahjoub, Ali Ridha
Publisher
Wiley
Published in
London
ISBN
9781848212060
Number of pages
416
Metadata
Show full item record
Author(s)
Paschos, Vangelis
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 / Keywords
Approximation algorithms; Exponential algorithms