Moderately exponential time and fixed parameter approximation algorithms
Bruno Escoffier, Vangélis Th. Paschos, Émeric Tourniaire · Optimization · 2012
We survey approximation issues matching ideas and tools from the fields of polynomial approximation, moderately exponential computation and fixed parameter tractability aiming at designing 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. This research programme, despite its relative youth, is becoming very active in computer science and in combinatorial optimization and motivates extensive research.