Google Research

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

Algorithms, vol. 13(6) (2020), pp. 146

Abstract

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work