Parameterized approximation algorithm

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. 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 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 f(k)n^{O(1)} time, where f(k) 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 f(k)n^{O(1)} time, where f(k) is a function independent of the input size .…

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. 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 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 f(k)n^{O(1)} time, where f(k) 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 f(k)n^{O(1)} time, where f(k) 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. 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 . For example, while the Connected Vertex Cover problem is FPT parameterized by the solution size, it does not admit a (regular) polynomial sized kernel (unless \textsf{NP}\subseteq \textsf{coNP/poly} ), 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 \textsf{NP}\subseteq \textsf{coNP/poly} ), but a PSAKS exists. When parameterizing Steiner Tree by the number of non-terminals in the optimum solution, the problem is W[2]-hard (and thus admits no exact kernel at all, unless FPT=W[2]), but still admits a PSAKS. Daniel Lokshtanov: A Parameterized Approximation Scheme for k-Min Cut Tuukka Korhonen: Single-Exponential Time 2-Approximation Algorithm for Treewidth Karthik C. S.: Recent Hardness of Approximation results in Parameterized Complexity Ariel Kulik. Two-variable Recurrence Relations with Application to Parameterized Approximations Meirav Zehavi. FPT Approximation Vincent Cohen-Added: On the Parameterized Complexity of Various Clustering Problems Fahad Panolan. Parameterized Approximation for Independent Set of Rectangles Andreas Emil Feldmann. Approximate Kernelization Schemes for Steiner Networks

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368633902 under CC BY-SA 4.0; modifications have been made.