A parameterized approximation algorithm is a type of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
that aims to find approximate solutions to
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
optimization problem
In mathematics, engineering, computer science and economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
s in
polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
s and
fixed-parameter tractability.
In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor away from the optimal solution, known as an -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 . 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
time, where
is a function independent of the input size .
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
time, where
is a function independent of the input size . 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 utilized when a given
optimization problem
In mathematics, engineering, computer science and economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
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.,
), nor an FPT algorithm for the given parameter (i.e., it is at least
W hard">hard).
For example, some problems that are
APX-hard and
W hard">hard admit a parameterized approximation scheme (PAS), i.e., for any
a
-approximation can be computed in
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
, the value of
is assumed to be arbitrary but constant in order for the PAS to run in FPT time. If this assumption is unsatisfying,
is treated as a parameter as well to obtain an efficient parameterized approximation scheme (EPAS), which for any
computes a
-approximation in
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
-approximation algorithm for any
, assuming
and the
small set expansion hypothesis. It is also W
hard parameterized by the number of required components. However an EPAS exists, which computes a
-approximation in
time.
Travelling Salesman
The
Travelling Salesman problem
In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...
is
APX-hard and
paraNP-hard parameterized by the
doubling dimension (as it is
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
in the
Euclidean plane
In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
). However, an EPAS exists parameterized by the
doubling dimension, and even for the more general
highway dimension The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. It was first formally defined by Abraham et al. based on the observation by Bast et al. that any road network ha ...
parameter.
Steiner Tree
The
Steiner Tree problem
In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a ...
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
W hard">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
-approximation in
time.
The more general Steiner Forest problem is NP-hard on graphs of treewidth 3. However, on graphs of
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests
...
an EPAS can compute a
-approximation in
time.
Strongly-Connected Steiner Subgraph
It is known that the Strongly Connected Steiner Subgraph problem is W
hard parameterized by the number of terminals, and also does not admit an
-approximation in polynomial time (under standard
complexity assumptions). However a 2-approximation can be computed in
time. Furthermore, this is best possible, since no
-approximation can be computed in
time for any function , under Gap-
ETH
Eth ( , uppercase: ⟨Ð⟩, lowercase: ⟨ð⟩; also spelled edh or eð), known as in Old English, is a letter used in Old English, Middle English, Icelandic, Faroese (in which it is called ), and Elfdalian.
It was also used in Sca ...
.
''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
-approximation for k-Median and no
-approximation for k-Means can be computed in
time for any function , under Gap-
ETH
Eth ( , uppercase: ⟨Ð⟩, lowercase: ⟨ð⟩; also spelled edh or eð), known as in Old English, is a letter used in Old English, Middle English, Icelandic, Faroese (in which it is called ), and Elfdalian.
It was also used in Sca ...
.
Matching parameterized approximation algorithms exist,
but it is not known whether matching approximations can be computed in polynomial time.
Clustering is often considered in settings of low dimensional data, and thus a practically relevant parameterization is by the
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coo ...
of the underlying
metric
Metric or metrical may refer to:
Measuring
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
...
. In the
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
, the k-Median and k-Means problems admit an EPAS parameterized by the dimension , 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 The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. It was first formally defined by Abraham et al. based on the observation by Bast et al. that any road network ha ...
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
Taxicab geometry or Manhattan geometry is geometry where the familiar Euclidean distance is ignored, and the distance between two point (geometry), points is instead defined to be the sum of the absolute differences of their respective Cartesian ...
), or the
highway dimension The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. It was first formally defined by Abraham et al. based on the observation by Bast et al. that any road network ha ...
,
no parameterized
-approximation algorithm exists, under standard
complexity assumptions. Furthermore, the k-Center problem is W
hard even on
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s when simultaneously parameterizing it by the number of centers, the
doubling dimension, the
highway dimension The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. It was first formally defined by Abraham et al. based on the observation by Bast et al. that any road network ha ...
, and the
pathwidth.
However, when combining with the doubling dimension an EPAS exists,
and the same is true when combining with the
highway dimension The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. It was first formally defined by Abraham et al. based on the observation by Bast et al. that any road network ha ...
. 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
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests
...
parameter, and also for
cliquewidth.
Densest Subgraph
An
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
variant of the
''k''-Clique problem is the Densest ''k''-Subgraph problem (which is a 2-ary
Constraint Satisfaction problem
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite const ...
), where the task is to find a subgraph on vertices with maximum number of edges. It is not hard to obtain a
-approximation by just picking a
matching of size
in the given input graph, since the maximum number of edges on vertices is always at most
. This is also
asymptotically
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
optimal, since under Gap-
ETH
Eth ( , uppercase: ⟨Ð⟩, lowercase: ⟨ð⟩; also spelled edh or eð), known as in Old English, is a letter used in Old English, Middle English, Icelandic, Faroese (in which it is called ), and Elfdalian.
It was also used in Sca ...
no
-approximation can be computed in FPT time parameterized by .
Dominating Set
For the
Dominating set problem it is W
hard to compute any
-approximation in
time for any functions and .
Approximate kernelization
Kernelization
In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solvi ...
is a technique used in
fixed-parameter tractability to pre-process an instance of an
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
problem in order to remove "easy parts" and reveal the NP-hard core of the instance. A kernelization algorithm takes an instance and a parameter , and returns a new instance
with parameter
such that the size of
and
is bounded as a function of the input parameter , and the algorithm runs in polynomial time. An -approximate kernelization algorithm is a variation of this technique that is used in parameterized approximation algorithms. It returns a kernel
such that any -approximation in
can be converted into an -approximation to the input instance in polynomial time. This notion was introduced by Lokshtanov et al.,
but there are other related notions in the literature such as Turing kernels and -fidelity kernelization.
As for regular (non-approximate) kernels, a problem admits an α-approximate kernelization algorithm
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
it has a parameterized α-approximation algorithm. The proof of this fact is very similar to
the one for regular kernels.
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. Furthermore, a polynomial-sized approximate kernelization scheme (PSAKS) is an -approximate kernelization algorithm that computes a polynomial-sized kernel and for which can be set to
for any
.
For example, while the Connected
Vertex Cover
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...
problem is FPT parameterized by the solution size, it does not admit a (regular) polynomial sized kernel (unless
), but a PSAKS exists.
Similarly, the Steiner Tree problem is FPT parameterized by the number of terminals, does not admit a polynomial sized kernel (unless
), but a PSAKS exists.
When parameterizing Steiner Tree by the number of non-terminals in the optimum solution, the problem is W
hard (and thus admits no exact kernel at all, unless FPT=W
, but still admits a PSAKS.
Talks on parameterized approximations
Daniel Lokshtanov: A Parameterized Approximation Scheme for k-Min CutTuukka Korhonen: Single-Exponential Time 2-Approximation Algorithm for TreewidthKarthik C. S.: Recent Hardness of Approximation results in Parameterized ComplexityAriel Kulik. Two-variable Recurrence Relations with Application to Parameterized ApproximationsMeirav Zehavi. FPT ApproximationVincent Cohen-Added: On the Parameterized Complexity of Various Clustering ProblemsFahad Panolan. Parameterized Approximation for Independent Set of RectanglesAndreas Emil Feldmann. Approximate Kernelization Schemes for Steiner Networks
References
{{reflist
Algorithms
Approximation algorithms
Parameterized complexity