This paper proposes a way to bring together two seemingly "foreign" domains that are the polynomial approximation and the exact computation for NP-hard problems. We show how one can match ideas from both areas in order to design approximation algorithms achiev- ing ratios unachievable 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 apply these ideas to two famous combinatorial optimiza- tion problems, namely, the MAX INDEPENDENT SET and the MIN VERTEX COVER, as well as to some other problems mainly linked to max independent set by simple approximation preserving reductions.
