Parameterized approximation algorithm

A parameterized approximation algorithm is a method for finding approximate solutions to NP-hard optimization problems in time that is polynomial in the input size and some function of a chosen parameter, combining ideas from two separate traditions in algorithm design. Ordinary approximation algorithms guarantee a solution within a fixed factor of optimal in polynomial time, while fixed-parameter tractable algorithms find exact solutions in time that is polynomial in the input size plus a function of a parameter k; a parameterized approximation algorithm computes an alpha-approximate solution in f(k) times a polynomial in n, giving a stronger quality guarantee than a standard approximation while keeping the efficiency profile of a fixed-parameter tractable algorithm. Researchers including Marx, and later Feldmann and colleagues, have surveyed the area as a framework for computationally hard optimization problems.