A parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization problems in polynomial time in the input size and a function of a specific parameter.
On the other hand, parameterized algorithms are designed to find exact solutions to problems, but with the constraint that the running time of the algorithm is polynomial in the input size and a function of a specific parameter k. The parameter describes some property of the input and is small in typical applications.
The problem is said to be fixed-parameter tractable (FPT) if there is an algorithm that can find the optimum solution in
is a function independent of the input size n. A parameterized approximation algorithm aims to find a balance between these two approaches by finding approximate solutions in FPT time: the algorithm computes an α-approximation in
is a function independent of the input size n. This approach aims to overcome the limitations of both traditional approaches by having stronger guarantees on the solution quality compared to traditional approximations while still having efficient running times as in FPT algorithms.
An overview of the research area studying parameterized approximation algorithms can be found in the survey of Marx[1] and the more recent survey by Feldmann et al.[2] The full potential of parameterized approximation algorithms is utilized when a given optimization problem is shown to admit an α-approximation algorithm running in
time, while in contrast the problem neither has a polynomial-time α-approximation algorithm (under some complexity assumption, e.g.,
For example, some problems that are APX-hard and W[1]-hard admit a parameterized approximation scheme (PAS), i.e., for any
time for some functions f and g. This then circumvents the lower bounds in terms of polynomial-time approximation and fixed-parameter tractability.
A PAS is similar in spirit to a polynomial-time approximation scheme (PTAS) but additionally exploits a given parameter k. Since the degree of the polynomial in the runtime of a PAS depends on a function
is assumed to be arbitrary but constant in order for the PAS to run in FPT time.
is treated as a parameter as well to obtain an efficient parameterized approximation scheme (EPAS), which for any
time for some function f. This is similar in spirit to an efficient polynomial-time approximation scheme (EPTAS).
[5] The Steiner Tree problem is FPT parameterized by the number of terminals.
[6] However, for the "dual" parameter consisting of the number k of non-terminals contained in the optimum solution, the problem is W[2]-hard (due to a folklore reduction from the Dominating Set problem).
[8] The more general Steiner Forest problem is NP-hard on graphs of treewidth 3.
[9] It is known that the Strongly Connected Steiner Subgraph problem is W[1]-hard parameterized by the number k of terminals,[10] and also does not admit an
[13] For the well-studied metric clustering problems of k-median and k-means parameterized by the number k of centers, it is known that no
Clustering is often considered in settings of low dimensional data, and thus a practically relevant parameterization is by the dimension of the underlying metric.
[19] For the loosely related highway dimension parameter, only an approximation scheme with XP runtime is known to date.
[20] For the metric k-center problem a 2-approximation can be computed in polynomial time.
-approximation algorithm exists, under standard complexity assumptions.
[25] Regarding the pathwidth, k-Center admits an EPAS even for the more general treewidth parameter, and also for cliquewidth.
in the given input graph, since the maximum number of edges on k vertices is always at most
time for any functions g and f.[28] Kernelization is a technique used in fixed-parameter tractability to pre-process an instance of an NP-hard problem in order to remove "easy parts" and reveal the NP-hard core of the instance.
is bounded as a function of the input parameter k, and the algorithm runs in polynomial time.
can be converted into an αβ-approximation to the input instance I in polynomial time.
[29] However the guaranteed approximate kernel might be of exponential size (or worse) in the input parameter.
Hence it becomes interesting to find problems that admit polynomial sized approximate kernels.
[29] Similarly, the Steiner Tree problem is FPT parameterized by the number of terminals, does not admit a polynomial sized kernel (unless