Abstract (EN)

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