The full potential of parameterized approximation algorithms is utilized when a given
optimization problem is shown to admit an -approximation algorithm running in f(k)n^{O(1)} time, while in contrast the problem neither has a polynomial-time -approximation algorithm (under some
complexity assumption, e.g., \mathsf{P}\neq \mathsf{NP}), nor an FPT algorithm for the given parameter (i.e., it is at least Parameterized complexity#W hierarchy|W[1]-hard). For example, some problems that are
APX-hard and Parameterized complexity#W hierarchy|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 and . 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 . Since the degree of the polynomial in the runtime of a PAS depends on a function g(\varepsilon), the value of \varepsilon is assumed to be arbitrary but constant in order for the PAS to run in FPT time. If this assumption is unsatisfying, \varepsilon is treated as a parameter as well to 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 . This is similar in spirit to an
efficient polynomial-time approximation scheme (EPTAS). k-Cut The
k-cut problem has no polynomial-time (2-\varepsilon)-approximation algorithm for any \varepsilon>0, assuming \mathsf{P}\neq \mathsf{NP} and the
small set expansion hypothesis. It is also W[1]-hard parameterized by the number of required components. However an EPAS exists, which computes a (1+\varepsilon)-approximation in (k/\varepsilon)^{O(k)}n^{O(1)} time.
Travelling Salesman The
Travelling Salesman problem is
APX-hard and
paraNP-hard parameterized by the
doubling dimension (as it is
NP-hard in the
Euclidean plane). However, an EPAS exists parameterized by the
doubling dimension, and even for the more general
highway dimension parameter.
Steiner Tree The
Steiner Tree problem is FPT parameterized by the number of terminals. However, for the "dual" parameter consisting of the number of non-terminals contained in the optimum solution, the problem is Parameterized complexity#W hierarchy|W[2]-hard (due to a folklore reduction from the
Dominating Set problem). Steiner Tree is also known to be
APX-hard. However, there is an EPAS computing a (1+\varepsilon)-approximation in 2^{O(k^2/\varepsilon^4)}n^{O(1)} time. The more general Steiner Forest problem is NP-hard on graphs of treewidth 3. However, on graphs of
treewidth an EPAS can compute a (1+\varepsilon)-approximation in 2^{O(\frac{t^2}{\varepsilon}\log \frac{t}{\varepsilon})}n^{O(1)} time.
Strongly-Connected Steiner Subgraph It is known that the Strongly Connected Steiner Subgraph problem is W[1]-hard parameterized by the number of terminals, and also does not admit an O(\log^{2-\varepsilon} n)-approximation in polynomial time (under standard
complexity assumptions). However a 2-approximation can be computed in 3^{k}n^{O(1)} time. Furthermore, this is best possible, since no (2-\varepsilon)-approximation can be computed in f(k)n^{O(1)} time for any function , under Gap-
ETH.
k-Median and k-Means For the well-studied metric clustering problems of
k-median and
k-means parameterized by the number of centers, it is known that no (1+2/e-\varepsilon)-approximation for k-Median and no (1+8/e-\varepsilon)-approximation for k-Means can be computed in f(k)n^{O(1)} time for any function , under Gap-
ETH. Matching parameterized approximation algorithms exist, and also an EPAS parameterized by . The former was generalized to an EPAS for the parameterization by the
doubling dimension. For the loosely related
highway dimension parameter, only an approximation scheme with
XP runtime is known to date.
k-Center For the metric
k-center problem a 2-approximation can be computed in polynomial time. However, when parameterizing by either the number of centers, the
doubling dimension (in fact the dimension of a
Manhattan metric), or the
highway dimension, However, when combining with the doubling dimension an EPAS exists, For the more general version with vertex capacities, an EPAS exists for the parameterization by k and the doubling dimension, but not when using k and the highway dimension as the parameter. Regarding the pathwidth, k-Center admits an EPAS even for the more general
treewidth parameter, and also for
cliquewidth.
Densest Subgraph An
optimization variant of the
k-Clique problem is the Densest
k-Subgraph problem (which is a 2-ary
Constraint Satisfaction problem), where the task is to find a subgraph on vertices with maximum number of edges. It is not hard to obtain a (k-1)-approximation by just picking a
matching of size k/2 in the given input graph, since the maximum number of edges on vertices is always at most {k \choose 2}= k(k-1)/2. This is also
asymptotically optimal, since under Gap-
ETH no k^{1-o(1)}-approximation can be computed in FPT time parameterized by .
Dominating Set For the
Dominating set problem it is W[1]-hard to compute any g(k)-approximation in f(k)n^{O(1)} time for any functions and . == Approximate kernelization ==