Parameterized approximation algorithm

A parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard problems in polynomial time in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional approximation algorithms and fixed-parameter tractability.

In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor $\alpha$ away from the optimal solution, known as an $\alpha$-approximation, in polynomial time. 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 $f(k)n^{O(1)}$ time, where $f(k)$ 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 $\alpha$-approximation in $f(k)n^{O(1)}$ time, where $f(k)$ 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 and the more recent survey by Feldmann et al.

Obtainable approximation ratios

The full potential of parameterized approximation algorithms is used when a given optimization problem cannot be approximated in polynomial time within some ratio $\alpha$ (under some complexity assumption, e.g., $P\neq NP$), while at the same does not admit an FPT algorithm for a given parameter $k$ (i.e., it is at least W[1]-hard), but in contrast an $\alpha$-approximation can be computed in $f(k)n^{O(1)}$ time for the problem.

For example, some problems that are APX-hard and W[1]-hard admit a parameterized approximation scheme (PAS), i.e., for any $\varepsilon >0$ a $(1+\varepsilon )$-approximation can be computed in $f(k,\varepsilon )n^{g(\varepsilon )}$ time for some functions $f$ and $g$, thus circumventing 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 $g$ of $\varepsilon$, the value of $\varepsilon$ is assumed to be constant in order for the PAS to run in FPT time. When treating $\varepsilon$ as a parameter as well, we obtain an efficient parameterized approximation scheme (EPAS), which for any $\varepsilon >0$ computes a $(1+\varepsilon )$-approximation in $f(k,\varepsilon )n^{O(1)}$ time for some function $f$. This is similar in spirit to an efficient polynomial-time approximation scheme (EPTAS).

Clustering in low dimensional metrics

k-Median, k-Center: Euclidean, doubling and highway dimension

k-Cut

The k-cut problem has no polynomial-time $(2-\varepsilon )$-approximation algorithm for any $\varepsilon >0$, unless $P\neq NP$ and the Small Set Expansion Hypothesis, and is W[1]-hard parameterized by the number $k$ of required components. However an EPAS exists, which computes a $(1+\varepsilon )$-approximation in $(k/\varepsilon )^{O(k)}n^{O(1)}$ time.

Approximate kernelization

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. A kernelization algorithm takes an instance $I$ and a parameter $k$, and returns a new instance $I'$ with parameter $k'$ such that the size of $I'$ and $k'$ is bounded as a function of the input parameter $k$, and the algorithm runs in polynomial time. An $\alpha$-approximate kernelization algorithm is a variation of this technique that is used in parameterized approximation algorithms. It returns a kernel $I'$ such that any $\beta$-approximation in $I'$ can be converted into an $\alpha \beta$-approximation to the input instance $I$ in polynomial time. A polynomial-sized approximate kernelization scheme (PSAKS) is an $\alpha$-approximate kernelization algorithm that computes a polynomial-sized kernel and for which $\alpha$ can be set to $1+\varepsilon$ for any $\varepsilon >0$. This notion was introduced by Lokshtanov et al., but there are other related notions in the literature such as Turing kernels and $\alpha$-fidelity kernelization.

As for regular (non-approximative) kernels, a problem admits an α-approximate kernelization algorithm if and only if it has a parameterized α-approximation algorithm. The proof of this fact is very similar to the one for regular kernels.