Approximation by Moderately Exponential Algorithms

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.ou