Parameterized approximation algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 07:19, 14 April 2023

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 $\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^[1] and the more recent survey by Feldmann et al.^[2]

Obtainable approximation ratios

The full potential of parameterized approximation algorithms is utilized when a given optimization problem is shown to admit an $\alpha$ -approximation algorithm running in $f(k)n^{O(1)}$ time, while in contrast the problem neither has a polynomial-time $\alpha$ -approximation algorithm (under some complexity assumption, e.g., $P\neq NP$ ), nor an FPT algorithm for the given parameter $k$ (i.e., it is at least W[1]-hard).

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$ . 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 $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 $f$ . 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 $P\neq NP$ and the small set expansion hypothesis.^[3] It is also W[1]-hard parameterized by the number $k$ of required components.^[4] However an EPAS exists, which computes a $(1+\varepsilon )$ -approximation in $(k/\varepsilon )^{O(k)}n^{O(1)}$ time.^[5]

Steiner Tree

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). Steiner Tree is also known to be APX-hard.^[7] However, there is an EPAS computing a $(1+\varepsilon )$ -approximation in $2^{O(k^{2}/\varepsilon ^{4})}n^{O(1)}$ time.^[8]

Strongly Connected Steiner Subgraph

It is known that the Strongly Connected Steiner Subgraph problem is W[1]-hard parameterized by the number $k$ of terminals,^[9] and also does not admit an $O(\log ^{2-\varepsilon }n)$ -approximation in polynomial time (under standard complexity assumptions).^[10] However a 2-approximation can be computed in $3^{k}n^{O(1)}$ time.^[11] Furthermore, this is best possible, since no $(2-\varepsilon )$ -approximation can be computed in $f(k)n^{O(1)}$ time for any function $f$ , under Gap-ETH.^[12]

k-Median and k-Means

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 $(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 $f$ , under Gap-ETH.^[13] Matching parameterized approximation algorithms exist,^[13] 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 of the underlying metric. In the Euclidean space, the k-Median and k-Means problems admit an EPAS parameterized by the dimension $d$ ,^[14]^[15] and also an EPAS parameterized by $k$ .^[16]^[17] The former was generalized to an EPAS for the parameterization by the doubling dimension.^[18] For the loosely related highway dimension parameter, only an approximation scheme with XP runtime is known to date.^[19]

k-Center

For the metric k-Center problem a 2-approximation can be computed in polynomial time. However, when parameterizing by either the number $k$ of centers,^[20] the doubling dimension (in fact the dimension of a Manhattan metric),^[21] or the highway dimension,^[20] no parameterized $(2-\varepsilon )$ -approximation algorithm exists, under standard complexity assumptions. Furthermore, the k-Center problem is W[1]-hard even on planar graphs when simultaneously parameterizing it by the number $k$ of centers, the doubling dimension, the highway dimension, and the pathwidth.^[22] However, when combining $k$ with the doubling dimension an EPAS exists,^[22] and the same is true when combining $k$ with the highway dimension.^[23] 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.^[24] Regarding the pathwidth, k-Center admits an EPAS even for the more general treewidth parameter, and also for cliquewidth.^[25]

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 $k$ 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 $k$ 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 $k$ .^[26]

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 $g$ and $f$ .^[27]

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. This notion was introduced by Lokshtanov et al.,^[28] but there are other related notions in the literature such as Turing kernels^[29] and $\alpha$ -fidelity kernelization.^[30]

As for regular (non-approximate) 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.^[28] 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 $\alpha$ -approximate kernelization algorithm that computes a polynomial-sized kernel and for which $\alpha$ can be set to $1+\varepsilon$ for any $\varepsilon >0$ .

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 $NP\subseteq coNP/poly$ ), but a PSAKS exists.^[28] Similarly, the Steiner Tree problem is FPT parameterized by the number of terminals, does not admit a polynomial sized kernel (unless $NP\subseteq coNP/poly$ ), but a PSAKS exists.^[28] 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.^[8]

References

^ Marx, Daniel (2008). "Parameterized Complexity and Approximation Algorithms". The Computer Journal. 51 (1): 60–78. doi:10.1093/comjnl/bxm048.
^ Feldmann, Andreas Emil; Karthik C. S; Lee, Euiwoong; Manurangsi, Pasin (2020). "A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms". Algorithms. 13 (6): 146. doi:10.3390/a13060146. ISSN 1999-4893. This article incorporates text from this source, which is available under the CC BY 4.0 license.
^ Manurangsi, Pasin (2018). "Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis". Algorithms. 11 (1): 10. doi:10.3390/a11010010. ISSN 1999-4893.
^ G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena; Rosamund, Frances A. (2003-04-01). "Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems". Electronic Notes in Theoretical Computer Science. CATS'03, Computing: the Australasian Theory Symposium. 78: 209–222. doi:10.1016/S1571-0661(04)81014-4. ISSN 1571-0661.
^ Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25). "A Parameterized Approximation Scheme for Min $k$-Cut". SIAM Journal on Computing: FOCS20–205. arXiv:2005.00134. doi:10.1137/20M1383197. ISSN 0097-5397.
^ Dreyfus, S. E.; Wagner, R. A. (1971). "The steiner problem in graphs". Networks. 1 (3): 195–207. doi:10.1002/net.3230010302.
^ Chlebík, Miroslav; Chlebíková, Janka (2008-10-31). "The Steiner tree problem on graphs: Inapproximability results". Theoretical Computer Science. Algorithmic Aspects of Global Computing. 406 (3): 207–214. doi:10.1016/j.tcs.2008.06.046. ISSN 0304-3975.
^ ^a ^b Dvořák, Pavel; Feldmann, Andreas E.; Knop, Dušan; Masařík, Tomáš; Toufar, Tomáš; Veselý, Pavel (2021-01-01). "Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices". SIAM Journal on Discrete Mathematics. 35 (1): 546–574. doi:10.1137/18M1209489. ISSN 0895-4801. S2CID 3581913.
^ Guo, Jiong; Niedermeier, Rolf; Suchý, Ondřej (2011-01-01). "Parameterized Complexity of Arc-Weighted Directed Steiner Problems". SIAM Journal on Discrete Mathematics. 25 (2): 583–599. doi:10.1137/100794560. ISSN 0895-4801.
^ Halperin, Eran; Krauthgamer, Robert (2003-06-09). "Polylogarithmic inapproximability". Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing. STOC '03. New York, NY, USA: Association for Computing Machinery: 585–594. doi:10.1145/780542.780628. ISBN 978-1-58113-674-6. S2CID 8554166.
^ Chitnis, Rajesh; Hajiaghayi, MohammadTaghi; Kortsarz, Guy (2013). Gutin, Gregory; Szeider, Stefan (eds.). "Fixed-Parameter and Approximation Algorithms: A New Look". Parameterized and Exact Computation. Lecture Notes in Computer Science. 8246. Cham: Springer International Publishing: 110–122. arXiv:1308.3520. doi:10.1007/978-3-319-03898-8_11. ISBN 978-3-319-03898-8. S2CID 6796132.
^ Chitnis, Rajesh; Feldmann, Andreas Emil; Manurangsi, Pasin (2021-04-19). "Parameterized Approximation Algorithms for Bidirected Steiner Network Problems". ACM Transactions on Algorithms. 17 (2): 12:1–12:68. doi:10.1145/3447584. ISSN 1549-6325. S2CID 235372580.
^ ^a ^b Cohen-Addad, Vincent; Gupta, Anupam; Kumar, Amit; Lee, Euiwoong; Li, Jason (2019). Baier, Christel; Chatzigiannakis, Ioannis; Flocchini, Paola; Leonardi, Stefano (eds.). "Tight FPT Approximations for k-Median and k-Means". 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs). 132. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 42:1–42:14. doi:10.4230/LIPIcs.ICALP.2019.42. ISBN 978-3-95977-109-2. S2CID 139103417.
^ Kolliopoulos, Stavros G.; Rao, Satish (1999), Nešetřil, Jaroslav (ed.), "A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem", Algorithms - ESA’ 99, vol. 1643, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 378–389, doi:10.1007/3-540-48481-7_33, ISBN 978-3-540-66251-8, retrieved 2023-01-24
^ Cohen-Addad, Vincent (2018-01-01), "A Fast Approximation Scheme for Low-Dimensional k-Means", Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 430–440, doi:10.1137/1.9781611975031.29, ISBN 978-1-61197-503-1, S2CID 30474859, retrieved 2023-01-24
^ Feldman, Dan; Monemizadeh, Morteza; Sohler, Christian (2007-06-06). "A PTAS for k-means clustering based on weak coresets". Proceedings of the Twenty-third Annual Symposium on Computational Geometry. SCG '07. New York, NY, USA: Association for Computing Machinery: 11–18. doi:10.1145/1247069.1247072. ISBN 978-1-59593-705-6. S2CID 5694112.
^ Feldman, Dan; Langberg, Michael (2011-06-06). "A unified framework for approximating and clustering data". Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing. STOC '11. New York, NY, USA: Association for Computing Machinery: 569–578. doi:10.1145/1993636.1993712. ISBN 978-1-4503-0691-1. S2CID 2677556.
^ Cohen-Addad, Vincent; Feldmann, Andreas Emil; Saulpic, David (2021-10-31). "Near-linear Time Approximation Schemes for Clustering in Doubling Metrics". Journal of the ACM. 68 (6): 44:1–44:34. arXiv:1812.08664. doi:10.1145/3477541. ISSN 0004-5411. S2CID 240476191.
^ Feldmann, Andreas Emil; Saulpic, David (2021-12-01). "Polynomial time approximation schemes for clustering in low highway dimension graphs". Journal of Computer and System Sciences. 122: 72–93. doi:10.1016/j.jcss.2021.06.002. ISSN 0022-0000.
^ ^a ^b Feldmann, Andreas Emil (2019-03-01). "Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs". Algorithmica. 81 (3): 1031–1052. arXiv:1605.02530. doi:10.1007/s00453-018-0455-0. ISSN 1432-0541. S2CID 46886829.
^ Feder, Tomás; Greene, Daniel (1988-01-01). "Optimal algorithms for approximate clustering". Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC '88. New York, NY, USA: Association for Computing Machinery: 434–444. doi:10.1145/62212.62255. ISBN 978-0-89791-264-8. S2CID 658151.
^ ^a ^b Feldmann, Andreas Emil; Marx, Dániel (2020-07-01). "The Parameterized Hardness of the k-Center Problem in Transportation Networks". Algorithmica. 82 (7): 1989–2005. doi:10.1007/s00453-020-00683-w. ISSN 1432-0541. S2CID 3532236.
^ Becker, Amariah; Klein, Philip N.; Saulpic, David (2018). Azar, Yossi; Bast, Hannah; Herman, Grzegorz (eds.). "Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension". 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs). 112. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 8:1–8:15. doi:10.4230/LIPIcs.ESA.2018.8. ISBN 978-3-95977-081-1.
^ Feldmann, Andreas Emil; Vu, Tung Anh (2022). Bekos, Michael A.; Kaufmann, Michael (eds.). "Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension". Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science. 13453. Cham: Springer International Publishing: 215–229. arXiv:2209.00675. doi:10.1007/978-3-031-15914-5_16. ISBN 978-3-031-15914-5.
^ Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis Th. (2019-07-15). "Structural parameters, tight bounds, and approximation for (k,r)-center". Discrete Applied Mathematics. Combinatorial Optimization: between Practice and Theory. 264: 90–117. doi:10.1016/j.dam.2018.11.002. ISSN 0166-218X.
^ Dinur, Irit; Manurangsi, Pasin (2018). Karlin, Anna R. (ed.). "ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network". 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs). 94. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:20. doi:10.4230/LIPIcs.ITCS.2018.36. ISBN 978-3-95977-060-6. S2CID 4681120.
^ S., Karthik C.; Laekhanukit, Bundit; Manurangsi, Pasin (2018-06-20). "On the parameterized complexity of approximating dominating set". Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018. New York, NY, USA: Association for Computing Machinery: 1283–1296. arXiv:1711.11029. doi:10.1145/3188745.3188896. ISBN 978-1-4503-5559-9. S2CID 3170316.
^ ^a ^b ^c ^d Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket (2017-06-19). "Lossy kernelization". Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2017. New York, NY, USA: Association for Computing Machinery: 224–237. doi:10.1145/3055399.3055456. ISBN 978-1-4503-4528-6. S2CID 14599219.
^ Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi (2015-03-01). "A Completeness Theory for Polynomial (Turing) Kernelization". Algorithmica. 71 (3): 702–730. doi:10.1007/s00453-014-9910-8. ISSN 1432-0541. S2CID 253973283.
^ Fellows, Michael R.; Kulik, Ariel; Rosamond, Frances; Shachnai, Hadas (2018-05-01). "Parameterized approximation via fidelity preserving transformations". Journal of Computer and System Sciences. 93: 30–40. doi:10.1016/j.jcss.2017.11.001. ISSN 0022-0000.

[1] Marx, Daniel (2008). "Parameterized Complexity and Approximation Algorithms". The Computer Journal. 51 (1): 60–78. doi:10.1093/comjnl/bxm048.

[2] Feldmann, Andreas Emil; Karthik C. S; Lee, Euiwoong; Manurangsi, Pasin (2020). "A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms". Algorithms. 13 (6): 146. doi:10.3390/a13060146. ISSN 1999-4893. This article incorporates text from this source, which is available under the CC BY 4.0 license.

[3] Manurangsi, Pasin (2018). "Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis". Algorithms. 11 (1): 10. doi:10.3390/a11010010. ISSN 1999-4893.

[4] G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena; Rosamund, Frances A. (2003-04-01). "Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems". Electronic Notes in Theoretical Computer Science. CATS'03, Computing: the Australasian Theory Symposium. 78: 209–222. doi:10.1016/S1571-0661(04)81014-4. ISSN 1571-0661.

[5] Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25). "A Parameterized Approximation Scheme for Min $k$-Cut". SIAM Journal on Computing: FOCS20–205. arXiv:2005.00134. doi:10.1137/20M1383197. ISSN 0097-5397.

[6] Dreyfus, S. E.; Wagner, R. A. (1971). "The steiner problem in graphs". Networks. 1 (3): 195–207. doi:10.1002/net.3230010302.

[7] Chlebík, Miroslav; Chlebíková, Janka (2008-10-31). "The Steiner tree problem on graphs: Inapproximability results". Theoretical Computer Science. Algorithmic Aspects of Global Computing. 406 (3): 207–214. doi:10.1016/j.tcs.2008.06.046. ISSN 0304-3975.

[:5-8] Dvořák, Pavel; Feldmann, Andreas E.; Knop, Dušan; Masařík, Tomáš; Toufar, Tomáš; Veselý, Pavel (2021-01-01). "Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices". SIAM Journal on Discrete Mathematics. 35 (1): 546–574. doi:10.1137/18M1209489. ISSN 0895-4801. S2CID 3581913.

[9] Guo, Jiong; Niedermeier, Rolf; Suchý, Ondřej (2011-01-01). "Parameterized Complexity of Arc-Weighted Directed Steiner Problems". SIAM Journal on Discrete Mathematics. 25 (2): 583–599. doi:10.1137/100794560. ISSN 0895-4801.

[10] Halperin, Eran; Krauthgamer, Robert (2003-06-09). "Polylogarithmic inapproximability". Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing. STOC '03. New York, NY, USA: Association for Computing Machinery: 585–594. doi:10.1145/780542.780628. ISBN 978-1-58113-674-6. S2CID 8554166.

[11] Chitnis, Rajesh; Hajiaghayi, MohammadTaghi; Kortsarz, Guy (2013). Gutin, Gregory; Szeider, Stefan (eds.). "Fixed-Parameter and Approximation Algorithms: A New Look". Parameterized and Exact Computation. Lecture Notes in Computer Science. 8246. Cham: Springer International Publishing: 110–122. arXiv:1308.3520. doi:10.1007/978-3-319-03898-8_11. ISBN 978-3-319-03898-8. S2CID 6796132.

[12] Chitnis, Rajesh; Feldmann, Andreas Emil; Manurangsi, Pasin (2021-04-19). "Parameterized Approximation Algorithms for Bidirected Steiner Network Problems". ACM Transactions on Algorithms. 17 (2): 12:1–12:68. doi:10.1145/3447584. ISSN 1549-6325. S2CID 235372580.

[:1-13] Cohen-Addad, Vincent; Gupta, Anupam; Kumar, Amit; Lee, Euiwoong; Li, Jason (2019). Baier, Christel; Chatzigiannakis, Ioannis; Flocchini, Paola; Leonardi, Stefano (eds.). "Tight FPT Approximations for k-Median and k-Means". 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs). 132. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 42:1–42:14. doi:10.4230/LIPIcs.ICALP.2019.42. ISBN 978-3-95977-109-2. S2CID 139103417.

[14] Kolliopoulos, Stavros G.; Rao, Satish (1999), Nešetřil, Jaroslav (ed.), "A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem", Algorithms - ESA’ 99, vol. 1643, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 378–389, doi:10.1007/3-540-48481-7_33, ISBN 978-3-540-66251-8, retrieved 2023-01-24

[15] Cohen-Addad, Vincent (2018-01-01), "A Fast Approximation Scheme for Low-Dimensional k-Means", Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 430–440, doi:10.1137/1.9781611975031.29, ISBN 978-1-61197-503-1, S2CID 30474859, retrieved 2023-01-24

[16] Feldman, Dan; Monemizadeh, Morteza; Sohler, Christian (2007-06-06). "A PTAS for k-means clustering based on weak coresets". Proceedings of the Twenty-third Annual Symposium on Computational Geometry. SCG '07. New York, NY, USA: Association for Computing Machinery: 11–18. doi:10.1145/1247069.1247072. ISBN 978-1-59593-705-6. S2CID 5694112.

[17] Feldman, Dan; Langberg, Michael (2011-06-06). "A unified framework for approximating and clustering data". Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing. STOC '11. New York, NY, USA: Association for Computing Machinery: 569–578. doi:10.1145/1993636.1993712. ISBN 978-1-4503-0691-1. S2CID 2677556.

[18] Cohen-Addad, Vincent; Feldmann, Andreas Emil; Saulpic, David (2021-10-31). "Near-linear Time Approximation Schemes for Clustering in Doubling Metrics". Journal of the ACM. 68 (6): 44:1–44:34. arXiv:1812.08664. doi:10.1145/3477541. ISSN 0004-5411. S2CID 240476191.

[19] Feldmann, Andreas Emil; Saulpic, David (2021-12-01). "Polynomial time approximation schemes for clustering in low highway dimension graphs". Journal of Computer and System Sciences. 122: 72–93. doi:10.1016/j.jcss.2021.06.002. ISSN 0022-0000.

[:2-20] Feldmann, Andreas Emil (2019-03-01). "Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs". Algorithmica. 81 (3): 1031–1052. arXiv:1605.02530. doi:10.1007/s00453-018-0455-0. ISSN 1432-0541. S2CID 46886829.

[21] Feder, Tomás; Greene, Daniel (1988-01-01). "Optimal algorithms for approximate clustering". Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC '88. New York, NY, USA: Association for Computing Machinery: 434–444. doi:10.1145/62212.62255. ISBN 978-0-89791-264-8. S2CID 658151.

[:3-22] Feldmann, Andreas Emil; Marx, Dániel (2020-07-01). "The Parameterized Hardness of the k-Center Problem in Transportation Networks". Algorithmica. 82 (7): 1989–2005. doi:10.1007/s00453-020-00683-w. ISSN 1432-0541. S2CID 3532236.

[23] Becker, Amariah; Klein, Philip N.; Saulpic, David (2018). Azar, Yossi; Bast, Hannah; Herman, Grzegorz (eds.). "Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension". 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs). 112. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 8:1–8:15. doi:10.4230/LIPIcs.ESA.2018.8. ISBN 978-3-95977-081-1.

[24] Feldmann, Andreas Emil; Vu, Tung Anh (2022). Bekos, Michael A.; Kaufmann, Michael (eds.). "Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension". Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science. 13453. Cham: Springer International Publishing: 215–229. arXiv:2209.00675. doi:10.1007/978-3-031-15914-5_16. ISBN 978-3-031-15914-5.

[:4-25] Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis Th. (2019-07-15). "Structural parameters, tight bounds, and approximation for (k,r)-center". Discrete Applied Mathematics. Combinatorial Optimization: between Practice and Theory. 264: 90–117. doi:10.1016/j.dam.2018.11.002. ISSN 0166-218X.

[26] Dinur, Irit; Manurangsi, Pasin (2018). Karlin, Anna R. (ed.). "ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network". 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs). 94. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:20. doi:10.4230/LIPIcs.ITCS.2018.36. ISBN 978-3-95977-060-6. S2CID 4681120.

[27] S., Karthik C.; Laekhanukit, Bundit; Manurangsi, Pasin (2018-06-20). "On the parameterized complexity of approximating dominating set". Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018. New York, NY, USA: Association for Computing Machinery: 1283–1296. arXiv:1711.11029. doi:10.1145/3188745.3188896. ISBN 978-1-4503-5559-9. S2CID 3170316.

[:0-28] Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket (2017-06-19). "Lossy kernelization". Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2017. New York, NY, USA: Association for Computing Machinery: 224–237. doi:10.1145/3055399.3055456. ISBN 978-1-4503-4528-6. S2CID 14599219.

[29] Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi (2015-03-01). "A Completeness Theory for Polynomial (Turing) Kernelization". Algorithmica. 71 (3): 702–730. doi:10.1007/s00453-014-9910-8. ISSN 1432-0541. S2CID 253973283.

[30] Fellows, Michael R.; Kulik, Ariel; Rosamond, Frances; Shachnai, Hadas (2018-05-01). "Parameterized approximation via fidelity preserving transformations". Journal of Computer and System Sciences. 93: 30–40. doi:10.1016/j.jcss.2017.11.001. ISSN 0022-0000.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

@@ Line 5: / Line 5: @@
 In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor <math>\alpha</math> away from the optimal solution, known as an <math>\alpha</math>-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 <math>k</math>. 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 <math>f(k)n^{O(1)}</math> time, where <math>f(k)</math> is a function independent of the input size <math>n</math>.
-A parameterized approximation algorithm aims to find a balance between these two approaches by finding approximate solutions in FPT time: the algorithm computes an <math>\alpha</math>-approximation in <math>f(k)n^{O(1)}</math> time, where <math>f(k)</math> is a function independent of the input size <math>n</math>. 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<ref>{{Cite journal |last=Marx |first=Daniel |date=2008 |title=Parameterized Complexity and Approximation Algorithms |url=https://doi.org/10.1093/comjnl/bxm048 |journal=The Computer Journal |volume=51 |issue=1 |pages=60-78}}</ref> and the more recent survey by Feldmann et al.<ref>{{Cite journal |last=Feldmann |first=Andreas Emil |last2=Karthik C. S |last3=Lee |first3=Euiwoong |last4=Manurangsi |first4=Pasin |date=2020 |title=A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms |url=https://www.mdpi.com/1999-4893/13/6/146 |journal=Algorithms |language=en |volume=13 |issue=6 |pages=146 |doi=10.3390/a13060146 |issn=1999-4893}}{{Creative Commons text attribution notice|cc=by4|from this source=yes}}
+A parameterized approximation algorithm aims to find a balance between these two approaches by finding approximate solutions in FPT time: the algorithm computes an <math>\alpha</math>-approximation in <math>f(k)n^{O(1)}</math> time, where <math>f(k)</math> is a function independent of the input size <math>n</math>. 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<ref>{{Cite journal |last=Marx |first=Daniel |date=2008 |title=Parameterized Complexity and Approximation Algorithms |url=https://doi.org/10.1093/comjnl/bxm048 |journal=The Computer Journal |volume=51 |issue=1 |pages=60–78|doi=10.1093/comjnl/bxm048 }}</ref> and the more recent survey by Feldmann et al.<ref>{{Cite journal |last1=Feldmann |first1=Andreas Emil |last2=Karthik C. S |last3=Lee |first3=Euiwoong |last4=Manurangsi |first4=Pasin |date=2020 |title=A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms |journal=Algorithms |language=en |volume=13 |issue=6 |pages=146 |doi=10.3390/a13060146 |issn=1999-4893 |doi-access=free }}{{Creative Commons text attribution notice|cc=by4|from this source=yes}}
 </ref>
@@ Line 14: / Line 14: @@
 === k-Cut ===
-The [[Minimum k-cut|k-cut]] problem has no polynomial-time <math>(2-\varepsilon)</math>-approximation algorithm for any <math>\varepsilon>0</math>, assuming <math>P\neq NP</math> and the [[small set expansion hypothesis]].<ref>{{Cite journal |last=Manurangsi |first=Pasin |date=2018 |title=Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis |url=https://www.mdpi.com/1999-4893/11/1/10 |journal=Algorithms |language=en |volume=11 |issue=1 |pages=10 |doi=10.3390/a11010010 |issn=1999-4893}}</ref> It is also W[1]-hard parameterized by the number <math>k</math> of required components.<ref>{{Cite journal |last=G. Downey |first=Rodney |last2=Estivill-Castro |first2=Vladimir |last3=Fellows |first3=Michael |last4=Prieto |first4=Elena |last5=Rosamund |first5=Frances A. |date=2003-04-01 |title=Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems |url=https://www.sciencedirect.com/science/article/pii/S1571066104810144 |journal=Electronic Notes in Theoretical Computer Science |series=CATS'03, Computing: the Australasian Theory Symposium |language=en |volume=78 |pages=209–222 |doi=10.1016/S1571-0661(04)81014-4 |issn=1571-0661}}</ref> However an EPAS exists, which computes a <math>(1+\varepsilon)</math>-approximation in <math>(k/\varepsilon)^{O(k)}n^{O(1)}</math> time.<ref>{{Cite journal |last=Lokshtanov |first=Daniel |last2=Saurabh |first2=Saket |last3=Surianarayanan |first3=Vaishali |date=2022-04-25 |title=A Parameterized Approximation Scheme for Min $k$-Cut |url=https://epubs.siam.org/doi/10.1137/20M1383197 |journal=SIAM Journal on Computing |pages=FOCS20–205 |doi=10.1137/20M1383197 |issn=0097-5397}}</ref>
+The [[Minimum k-cut|k-cut]] problem has no polynomial-time <math>(2-\varepsilon)</math>-approximation algorithm for any <math>\varepsilon>0</math>, assuming <math>P\neq NP</math> and the [[small set expansion hypothesis]].<ref>{{Cite journal |last=Manurangsi |first=Pasin |date=2018 |title=Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis |journal=Algorithms |language=en |volume=11 |issue=1 |pages=10 |doi=10.3390/a11010010 |issn=1999-4893 |doi-access=free }}</ref> It is also W[1]-hard parameterized by the number <math>k</math> of required components.<ref>{{Cite journal |last1=G. Downey |first1=Rodney |last2=Estivill-Castro |first2=Vladimir |last3=Fellows |first3=Michael |last4=Prieto |first4=Elena |last5=Rosamund |first5=Frances A. |date=2003-04-01 |title=Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems |url=https://www.sciencedirect.com/science/article/pii/S1571066104810144 |journal=Electronic Notes in Theoretical Computer Science |series=CATS'03, Computing: the Australasian Theory Symposium |language=en |volume=78 |pages=209–222 |doi=10.1016/S1571-0661(04)81014-4 |issn=1571-0661}}</ref> However an EPAS exists, which computes a <math>(1+\varepsilon)</math>-approximation in <math>(k/\varepsilon)^{O(k)}n^{O(1)}</math> time.<ref>{{Cite journal |last1=Lokshtanov |first1=Daniel |last2=Saurabh |first2=Saket |last3=Surianarayanan |first3=Vaishali |date=2022-04-25 |title=A Parameterized Approximation Scheme for Min $k$-Cut |url=https://epubs.siam.org/doi/10.1137/20M1383197 |journal=SIAM Journal on Computing |pages=FOCS20–205 |doi=10.1137/20M1383197 |arxiv=2005.00134 |issn=0097-5397}}</ref>
 === Steiner Tree ===
-The [[Steiner tree problem|Steiner Tree problem]] is FPT parameterized by the number of terminals.<ref>{{Cite journal |last=Dreyfus |first=S. E. |last2=Wagner |first2=R. A. |date=1971 |title=The steiner problem in graphs |url=https://onlinelibrary.wiley.com/doi/10.1002/net.3230010302 |journal=Networks |language=en |volume=1 |issue=3 |pages=195–207 |doi=10.1002/net.3230010302}}</ref> However for the "dual" parameter consisting of the number <math>k</math> 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|Dominating Set problem]]). Steiner Tree is also known to be [[APX|APX-hard]].<ref>{{Cite journal |last=Chlebík |first=Miroslav |last2=Chlebíková |first2=Janka |date=2008-10-31 |title=The Steiner tree problem on graphs: Inapproximability results |url=https://www.sciencedirect.com/science/article/pii/S0304397508004660 |journal=Theoretical Computer Science |series=Algorithmic Aspects of Global Computing |language=en |volume=406 |issue=3 |pages=207–214 |doi=10.1016/j.tcs.2008.06.046 |issn=0304-3975}}</ref> However, there is an EPAS computing a <math>(1+\varepsilon)</math>-approximation in <math>2^{O(k^2/\varepsilon^4)}n^{O(1)}</math> time.<ref name=":5">{{Cite journal |last=Dvořák |first=Pavel |last2=Feldmann |first2=Andreas E. |last3=Knop |first3=Dušan |last4=Masařík |first4=Tomáš |last5=Toufar |first5=Tomáš |last6=Veselý |first6=Pavel |date=2021-01-01 |title=Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices |url=https://epubs.siam.org/doi/10.1137/18M1209489 |journal=SIAM Journal on Discrete Mathematics |volume=35 |issue=1 |pages=546–574 |doi=10.1137/18M1209489 |issn=0895-4801}}</ref>
+The [[Steiner tree problem|Steiner Tree problem]] is FPT parameterized by the number of terminals.<ref>{{Cite journal |last1=Dreyfus |first1=S. E. |last2=Wagner |first2=R. A. |date=1971 |title=The steiner problem in graphs |url=https://onlinelibrary.wiley.com/doi/10.1002/net.3230010302 |journal=Networks |language=en |volume=1 |issue=3 |pages=195–207 |doi=10.1002/net.3230010302}}</ref> However for the "dual" parameter consisting of the number <math>k</math> 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|Dominating Set problem]]). Steiner Tree is also known to be [[APX|APX-hard]].<ref>{{Cite journal |last1=Chlebík |first1=Miroslav |last2=Chlebíková |first2=Janka |date=2008-10-31 |title=The Steiner tree problem on graphs: Inapproximability results |url=https://www.sciencedirect.com/science/article/pii/S0304397508004660 |journal=Theoretical Computer Science |series=Algorithmic Aspects of Global Computing |language=en |volume=406 |issue=3 |pages=207–214 |doi=10.1016/j.tcs.2008.06.046 |issn=0304-3975}}</ref> However, there is an EPAS computing a <math>(1+\varepsilon)</math>-approximation in <math>2^{O(k^2/\varepsilon^4)}n^{O(1)}</math> time.<ref name=":5">{{Cite journal |last1=Dvořák |first1=Pavel |last2=Feldmann |first2=Andreas E. |last3=Knop |first3=Dušan |last4=Masařík |first4=Tomáš |last5=Toufar |first5=Tomáš |last6=Veselý |first6=Pavel |date=2021-01-01 |title=Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices |url=https://epubs.siam.org/doi/10.1137/18M1209489 |journal=SIAM Journal on Discrete Mathematics |volume=35 |issue=1 |pages=546–574 |doi=10.1137/18M1209489 |s2cid=3581913 |issn=0895-4801}}</ref>
 === Strongly Connected Steiner Subgraph ===
-It is known that the Strongly Connected Steiner Subgraph problem is W[1]-hard parameterized by the number <math>k</math> of terminals,<ref>{{Cite journal |last=Guo |first=Jiong |last2=Niedermeier |first2=Rolf |last3=Suchý |first3=Ondřej |date=2011-01-01 |title=Parameterized Complexity of Arc-Weighted Directed Steiner Problems |url=https://epubs.siam.org/doi/10.1137/100794560 |journal=SIAM Journal on Discrete Mathematics |volume=25 |issue=2 |pages=583–599 |doi=10.1137/100794560 |issn=0895-4801}}</ref> and also does not admit an <math>O(\log^{2-\varepsilon} n)</math>-approximation in polynomial time (under standard [[Computational complexity theory|complexity assumptions]]).<ref>{{Cite journal |last=Halperin |first=Eran |last2=Krauthgamer |first2=Robert |date=2003-06-09 |title=Polylogarithmic inapproximability |url=https://doi.org/10.1145/780542.780628 |journal=Proceedings of the thirty-fifth annual ACM symposium on Theory of computing |series=STOC '03 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=585–594 |doi=10.1145/780542.780628 |isbn=978-1-58113-674-6}}</ref> However a 2-approximation can be computed in <math>3^{k}n^{O(1)}</math> time.<ref>{{Cite journal |last=Chitnis |first=Rajesh |last2=Hajiaghayi |first2=MohammadTaghi |last3=Kortsarz |first3=Guy |date=2013 |editor-last=Gutin |editor-first=Gregory |editor2-last=Szeider |editor2-first=Stefan |title=Fixed-Parameter and Approximation Algorithms: A New Look |url=https://link.springer.com/chapter/10.1007/978-3-319-03898-8_11 |journal=Parameterized and Exact Computation |language=en |location=Cham |publisher=Springer International Publishing |pages=110–122 |doi=10.1007/978-3-319-03898-8_11 |isbn=978-3-319-03898-8}}</ref> Furthermore, this is best possible, since no <math>(2-\varepsilon)</math>-approximation can be computed in <math>f(k)n^{O(1)}</math> time for any function <math>f</math>, under Gap-[[Exponential time hypothesis|ETH]].<ref>{{Cite journal |last=Chitnis |first=Rajesh |last2=Feldmann |first2=Andreas Emil |last3=Manurangsi |first3=Pasin |date=2021-04-19 |title=Parameterized Approximation Algorithms for Bidirected Steiner Network Problems |url=https://doi.org/10.1145/3447584 |journal=ACM Transactions on Algorithms |volume=17 |issue=2 |pages=12:1–12:68 |doi=10.1145/3447584 |issn=1549-6325}}</ref>
+It is known that the Strongly Connected Steiner Subgraph problem is W[1]-hard parameterized by the number <math>k</math> of terminals,<ref>{{Cite journal |last1=Guo |first1=Jiong |last2=Niedermeier |first2=Rolf |last3=Suchý |first3=Ondřej |date=2011-01-01 |title=Parameterized Complexity of Arc-Weighted Directed Steiner Problems |url=https://epubs.siam.org/doi/10.1137/100794560 |journal=SIAM Journal on Discrete Mathematics |volume=25 |issue=2 |pages=583–599 |doi=10.1137/100794560 |issn=0895-4801}}</ref> and also does not admit an <math>O(\log^{2-\varepsilon} n)</math>-approximation in polynomial time (under standard [[Computational complexity theory|complexity assumptions]]).<ref>{{Cite journal |last1=Halperin |first1=Eran |last2=Krauthgamer |first2=Robert |date=2003-06-09 |title=Polylogarithmic inapproximability |url=https://doi.org/10.1145/780542.780628 |journal=Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing |series=STOC '03 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=585–594 |doi=10.1145/780542.780628 |isbn=978-1-58113-674-6|s2cid=8554166 }}</ref> However a 2-approximation can be computed in <math>3^{k}n^{O(1)}</math> time.<ref>{{Cite journal |last1=Chitnis |first1=Rajesh |last2=Hajiaghayi |first2=MohammadTaghi |last3=Kortsarz |first3=Guy |date=2013 |editor-last=Gutin |editor-first=Gregory |editor2-last=Szeider |editor2-first=Stefan |title=Fixed-Parameter and Approximation Algorithms: A New Look |url=https://link.springer.com/chapter/10.1007/978-3-319-03898-8_11 |journal=Parameterized and Exact Computation |series=Lecture Notes in Computer Science |volume=8246 |language=en |location=Cham |publisher=Springer International Publishing |pages=110–122 |doi=10.1007/978-3-319-03898-8_11 |arxiv=1308.3520 |isbn=978-3-319-03898-8|s2cid=6796132 }}</ref> Furthermore, this is best possible, since no <math>(2-\varepsilon)</math>-approximation can be computed in <math>f(k)n^{O(1)}</math> time for any function <math>f</math>, under Gap-[[Exponential time hypothesis|ETH]].<ref>{{Cite journal |last1=Chitnis |first1=Rajesh |last2=Feldmann |first2=Andreas Emil |last3=Manurangsi |first3=Pasin |date=2021-04-19 |title=Parameterized Approximation Algorithms for Bidirected Steiner Network Problems |url=https://doi.org/10.1145/3447584 |journal=ACM Transactions on Algorithms |volume=17 |issue=2 |pages=12:1–12:68 |doi=10.1145/3447584 |s2cid=235372580 |issn=1549-6325}}</ref>
 === k-Median and k-Means ===
-For the well-studied metric clustering problems of [[K-median problem|k-Median]] and [[K-means clustering|k-Means]] parameterized by the number <math>k</math> of centers, it is known that no <math>(1+2/e-\varepsilon)</math>-approximation for k-Median and no <math>(1+8/e-\varepsilon)</math>-approximation for k-Means can be computed in <math>f(k)n^{O(1)}</math> time for any function <math>f</math>, under Gap-[[Exponential time hypothesis|ETH]].<ref name=":1">{{Cite journal |last=Cohen-Addad |first=Vincent |last2=Gupta |first2=Anupam |last3=Kumar |first3=Amit |last4=Lee |first4=Euiwoong |last5=Li |first5=Jason |date=2019 |editor-last=Baier |editor-first=Christel |editor2-last=Chatzigiannakis |editor2-first=Ioannis |editor3-last=Flocchini |editor3-first=Paola |editor4-last=Leonardi |editor4-first=Stefano |title=Tight FPT Approximations for k-Median and k-Means |url=http://drops.dagstuhl.de/opus/volltexte/2019/10618 |journal=46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=132 |pages=42:1–42:14 |doi=10.4230/LIPIcs.ICALP.2019.42 |isbn=978-3-95977-109-2}}</ref> Matching parameterized approximation algorithms exist,<ref name=":1" /> but it is not known whether matching approximations can be computed in polynomial time.
+For the well-studied metric clustering problems of [[K-median problem|k-Median]] and [[K-means clustering|k-Means]] parameterized by the number <math>k</math> of centers, it is known that no <math>(1+2/e-\varepsilon)</math>-approximation for k-Median and no <math>(1+8/e-\varepsilon)</math>-approximation for k-Means can be computed in <math>f(k)n^{O(1)}</math> time for any function <math>f</math>, under Gap-[[Exponential time hypothesis|ETH]].<ref name=":1">{{Cite journal |last1=Cohen-Addad |first1=Vincent |last2=Gupta |first2=Anupam |last3=Kumar |first3=Amit |last4=Lee |first4=Euiwoong |last5=Li |first5=Jason |date=2019 |editor-last=Baier |editor-first=Christel |editor2-last=Chatzigiannakis |editor2-first=Ioannis |editor3-last=Flocchini |editor3-first=Paola |editor4-last=Leonardi |editor4-first=Stefano |title=Tight FPT Approximations for k-Median and k-Means |url=http://drops.dagstuhl.de/opus/volltexte/2019/10618 |journal=46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=132 |pages=42:1–42:14 |doi=10.4230/LIPIcs.ICALP.2019.42 |isbn=978-3-95977-109-2|s2cid=139103417 }}</ref> Matching parameterized approximation algorithms exist,<ref name=":1" /> 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]] of the underlying [[Metric space|metric]]. In the [[Euclidean space]], the k-Median and k-Means problems admit an EPAS parameterized by the dimension <math>d</math>,<ref>{{Citation |last=Kolliopoulos |first=Stavros G. |title=A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem |date=1999 |url=http://link.springer.com/10.1007/3-540-48481-7_33 |work=Algorithms - ESA’ 99 |volume=1643 |pages=378–389 |editor-last=Nešetřil |editor-first=Jaroslav |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/3-540-48481-7_33 |isbn=978-3-540-66251-8 |access-date=2023-01-24 |last2=Rao |first2=Satish}}</ref><ref>{{Citation |last=Cohen-Addad |first=Vincent |title=A Fast Approximation Scheme for Low-Dimensional k-Means |date=2018-01-01 |url=https://epubs.siam.org/doi/10.1137/1.9781611975031.29 |work=Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=430–440 |series=Proceedings |publisher=Society for Industrial and Applied Mathematics |doi=10.1137/1.9781611975031.29 |access-date=2023-01-24}}</ref> and also an EPAS parameterized by <math>k</math>.<ref>{{Cite journal |last=Feldman |first=Dan |last2=Monemizadeh |first2=Morteza |last3=Sohler |first3=Christian |date=2007-06-06 |title=A PTAS for k-means clustering based on weak coresets |url=https://doi.org/10.1145/1247069.1247072 |journal=Proceedings of the twenty-third annual symposium on Computational geometry |series=SCG '07 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=11–18 |doi=10.1145/1247069.1247072 |isbn=978-1-59593-705-6}}</ref><ref>{{Cite journal |last=Feldman |first=Dan |last2=Langberg |first2=Michael |date=2011-06-06 |title=A unified framework for approximating and clustering data |url=https://doi.org/10.1145/1993636.1993712 |journal=Proceedings of the forty-third annual ACM symposium on Theory of computing |series=STOC '11 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=569–578 |doi=10.1145/1993636.1993712 |isbn=978-1-4503-0691-1}}</ref> The former was generalized to an EPAS for the parameterization by the [[Doubling space|doubling dimension]].<ref>{{Cite journal |last=Cohen-Addad |first=Vincent |last2=Feldmann |first2=Andreas Emil |last3=Saulpic |first3=David |date=2021-10-31 |title=Near-linear Time Approximation Schemes for Clustering in Doubling Metrics |url=https://doi.org/10.1145/3477541 |journal=Journal of the ACM |volume=68 |issue=6 |pages=44:1–44:34 |doi=10.1145/3477541 |issn=0004-5411}}</ref> For the loosely related highway dimension parameter, only an approximation scheme with [[Parameterized complexity|XP]] runtime is known to date.<ref>{{Cite journal |last=Feldmann |first=Andreas Emil |last2=Saulpic |first2=David |date=2021-12-01 |title=Polynomial time approximation schemes for clustering in low highway dimension graphs |url=https://www.sciencedirect.com/science/article/pii/S0022000021000647 |journal=Journal of Computer and System Sciences |language=en |volume=122 |pages=72–93 |doi=10.1016/j.jcss.2021.06.002 |issn=0022-0000}}</ref>
+Clustering is often considered in settings of low dimensional data, and thus a practically relevant parameterization is by the [[dimension]] of the underlying [[Metric space|metric]]. In the [[Euclidean space]], the k-Median and k-Means problems admit an EPAS parameterized by the dimension <math>d</math>,<ref>{{Citation |last1=Kolliopoulos |first1=Stavros G. |title=A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem |date=1999 |url=http://link.springer.com/10.1007/3-540-48481-7_33 |work=Algorithms - ESA’ 99 |volume=1643 |pages=378–389 |editor-last=Nešetřil |editor-first=Jaroslav |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/3-540-48481-7_33 |isbn=978-3-540-66251-8 |access-date=2023-01-24 |last2=Rao |first2=Satish}}</ref><ref>{{Citation |last=Cohen-Addad |first=Vincent |title=A Fast Approximation Scheme for Low-Dimensional k-Means |date=2018-01-01 |url=https://epubs.siam.org/doi/10.1137/1.9781611975031.29 |work=Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=430–440 |series=Proceedings |publisher=Society for Industrial and Applied Mathematics |doi=10.1137/1.9781611975031.29 |isbn=978-1-61197-503-1 |s2cid=30474859 |access-date=2023-01-24}}</ref> and also an EPAS parameterized by <math>k</math>.<ref>{{Cite journal |last1=Feldman |first1=Dan |last2=Monemizadeh |first2=Morteza |last3=Sohler |first3=Christian |date=2007-06-06 |title=A PTAS for k-means clustering based on weak coresets |url=https://doi.org/10.1145/1247069.1247072 |journal=Proceedings of the Twenty-third Annual Symposium on Computational Geometry |series=SCG '07 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=11–18 |doi=10.1145/1247069.1247072 |isbn=978-1-59593-705-6|s2cid=5694112 }}</ref><ref>{{Cite journal |last1=Feldman |first1=Dan |last2=Langberg |first2=Michael |date=2011-06-06 |title=A unified framework for approximating and clustering data |url=https://doi.org/10.1145/1993636.1993712 |journal=Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing |series=STOC '11 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=569–578 |doi=10.1145/1993636.1993712 |isbn=978-1-4503-0691-1|s2cid=2677556 }}</ref> The former was generalized to an EPAS for the parameterization by the [[Doubling space|doubling dimension]].<ref>{{Cite journal |last1=Cohen-Addad |first1=Vincent |last2=Feldmann |first2=Andreas Emil |last3=Saulpic |first3=David |date=2021-10-31 |title=Near-linear Time Approximation Schemes for Clustering in Doubling Metrics |url=https://doi.org/10.1145/3477541 |journal=Journal of the ACM |volume=68 |issue=6 |pages=44:1–44:34 |doi=10.1145/3477541 |arxiv=1812.08664 |s2cid=240476191 |issn=0004-5411}}</ref> For the loosely related highway dimension parameter, only an approximation scheme with [[Parameterized complexity|XP]] runtime is known to date.<ref>{{Cite journal |last1=Feldmann |first1=Andreas Emil |last2=Saulpic |first2=David |date=2021-12-01 |title=Polynomial time approximation schemes for clustering in low highway dimension graphs |url=https://www.sciencedirect.com/science/article/pii/S0022000021000647 |journal=Journal of Computer and System Sciences |language=en |volume=122 |pages=72–93 |doi=10.1016/j.jcss.2021.06.002 |issn=0022-0000}}</ref>
 === k-Center ===
-For the metric [[Metric k-center|k-Center problem]] a 2-approximation can be computed in polynomial time. However, when parameterizing by either the number <math>k</math> of centers,<ref name=":2">{{Cite journal |last=Feldmann |first=Andreas Emil |date=2019-03-01 |title=Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs |url=https://doi.org/10.1007/s00453-018-0455-0 |journal=Algorithmica |language=en |volume=81 |issue=3 |pages=1031–1052 |doi=10.1007/s00453-018-0455-0 |issn=1432-0541}}</ref> the [[Doubling space|doubling dimension]] (in fact the dimension of a [[Manhattan metric]]),<ref>{{Cite journal |last=Feder |first=Tomás |last2=Greene |first2=Daniel |date=1988-01-01 |title=Optimal algorithms for approximate clustering |url=https://doi.org/10.1145/62212.62255 |journal=Proceedings of the twentieth annual ACM symposium on Theory of computing |series=STOC '88 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=434–444 |doi=10.1145/62212.62255 |isbn=978-0-89791-264-8}}</ref> or the highway dimension,<ref name=":2" /> no parameterized <math>(2-\varepsilon)</math>-approximation algorithm exists, under standard [[Complexity theory (computation)|complexity assumptions]]. Furthermore, the k-Center problem is W[1]-hard even on [[Planar graph|planar graphs]] when simultaneously parameterizing it by the number <math>k</math> of centers, the [[Doubling space|doubling dimension]], the highway dimension, and the [[pathwidth]].<ref name=":3">{{Cite journal |last=Feldmann |first=Andreas Emil |last2=Marx |first2=Dániel |date=2020-07-01 |title=The Parameterized Hardness of the k-Center Problem in Transportation Networks |url=https://doi.org/10.1007/s00453-020-00683-w |journal=Algorithmica |language=en |volume=82 |issue=7 |pages=1989–2005 |doi=10.1007/s00453-020-00683-w |issn=1432-0541}}</ref> However, when combining <math>k</math> with the doubling dimension an EPAS exists,<ref name=":3" /> and the same is true when combining <math>k</math> with the highway dimension.<ref>{{Cite journal |last=Becker |first=Amariah |last2=Klein |first2=Philip N. |last3=Saulpic |first3=David |date=2018 |editor-last=Azar |editor-first=Yossi |editor2-last=Bast |editor2-first=Hannah |editor3-last=Herman |editor3-first=Grzegorz |title=Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension |url=http://drops.dagstuhl.de/opus/volltexte/2018/9471 |journal=26th Annual European Symposium on Algorithms (ESA 2018) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=112 |pages=8:1–8:15 |doi=10.4230/LIPIcs.ESA.2018.8 |isbn=978-3-95977-081-1}}</ref> 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.<ref>{{Cite journal |last=Feldmann |first=Andreas Emil |last2=Vu |first2=Tung Anh |date=2022 |editor-last=Bekos |editor-first=Michael A. |editor2-last=Kaufmann |editor2-first=Michael |title=Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension |url=https://link.springer.com/chapter/10.1007/978-3-031-15914-5_16 |journal=Graph-Theoretic Concepts  in Computer Science |language=en |location=Cham |publisher=Springer International Publishing |pages=215–229 |doi=10.1007/978-3-031-15914-5_16 |isbn=978-3-031-15914-5}}</ref> Regarding the pathwidth, k-Center admits an EPAS even for the more general [[treewidth]] parameter, and also for [[Clique-width|cliquewidth]].<ref name=":4">{{Cite journal |last=Katsikarelis |first=Ioannis |last2=Lampis |first2=Michael |last3=Paschos |first3=Vangelis Th. |date=2019-07-15 |title=Structural parameters, tight bounds, and approximation for (k,r)-center |url=https://www.sciencedirect.com/science/article/pii/S0166218X18306024 |journal=Discrete Applied Mathematics |series=Combinatorial Optimization: between Practice and Theory |language=en |volume=264 |pages=90–117 |doi=10.1016/j.dam.2018.11.002 |issn=0166-218X}}</ref>
+For the metric [[Metric k-center|k-Center problem]] a 2-approximation can be computed in polynomial time. However, when parameterizing by either the number <math>k</math> of centers,<ref name=":2">{{Cite journal |last=Feldmann |first=Andreas Emil |date=2019-03-01 |title=Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs |url=https://doi.org/10.1007/s00453-018-0455-0 |journal=Algorithmica |language=en |volume=81 |issue=3 |pages=1031–1052 |doi=10.1007/s00453-018-0455-0 |arxiv=1605.02530 |s2cid=46886829 |issn=1432-0541}}</ref> the [[Doubling space|doubling dimension]] (in fact the dimension of a [[Manhattan metric]]),<ref>{{Cite journal |last1=Feder |first1=Tomás |last2=Greene |first2=Daniel |date=1988-01-01 |title=Optimal algorithms for approximate clustering |url=https://doi.org/10.1145/62212.62255 |journal=Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing |series=STOC '88 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=434–444 |doi=10.1145/62212.62255 |isbn=978-0-89791-264-8|s2cid=658151 }}</ref> or the highway dimension,<ref name=":2" /> no parameterized <math>(2-\varepsilon)</math>-approximation algorithm exists, under standard [[Complexity theory (computation)|complexity assumptions]]. Furthermore, the k-Center problem is W[1]-hard even on [[Planar graph|planar graphs]] when simultaneously parameterizing it by the number <math>k</math> of centers, the [[Doubling space|doubling dimension]], the highway dimension, and the [[pathwidth]].<ref name=":3">{{Cite journal |last1=Feldmann |first1=Andreas Emil |last2=Marx |first2=Dániel |date=2020-07-01 |title=The Parameterized Hardness of the k-Center Problem in Transportation Networks |url=https://doi.org/10.1007/s00453-020-00683-w |journal=Algorithmica |language=en |volume=82 |issue=7 |pages=1989–2005 |doi=10.1007/s00453-020-00683-w |s2cid=3532236 |issn=1432-0541}}</ref> However, when combining <math>k</math> with the doubling dimension an EPAS exists,<ref name=":3" /> and the same is true when combining <math>k</math> with the highway dimension.<ref>{{Cite journal |last1=Becker |first1=Amariah |last2=Klein |first2=Philip N. |last3=Saulpic |first3=David |date=2018 |editor-last=Azar |editor-first=Yossi |editor2-last=Bast |editor2-first=Hannah |editor3-last=Herman |editor3-first=Grzegorz |title=Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension |url=http://drops.dagstuhl.de/opus/volltexte/2018/9471 |journal=26th Annual European Symposium on Algorithms (ESA 2018) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=112 |pages=8:1–8:15 |doi=10.4230/LIPIcs.ESA.2018.8 |isbn=978-3-95977-081-1}}</ref> 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.<ref>{{Cite journal |last1=Feldmann |first1=Andreas Emil |last2=Vu |first2=Tung Anh |date=2022 |editor-last=Bekos |editor-first=Michael A. |editor2-last=Kaufmann |editor2-first=Michael |title=Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension |url=https://link.springer.com/chapter/10.1007/978-3-031-15914-5_16 |journal=Graph-Theoretic Concepts in Computer Science |series=Lecture Notes in Computer Science |volume=13453 |language=en |location=Cham |publisher=Springer International Publishing |pages=215–229 |doi=10.1007/978-3-031-15914-5_16 |arxiv=2209.00675 |isbn=978-3-031-15914-5}}</ref> Regarding the pathwidth, k-Center admits an EPAS even for the more general [[treewidth]] parameter, and also for [[Clique-width|cliquewidth]].<ref name=":4">{{Cite journal |last1=Katsikarelis |first1=Ioannis |last2=Lampis |first2=Michael |last3=Paschos |first3=Vangelis Th. |date=2019-07-15 |title=Structural parameters, tight bounds, and approximation for (k,r)-center |url=https://www.sciencedirect.com/science/article/pii/S0166218X18306024 |journal=Discrete Applied Mathematics |series=Combinatorial Optimization: between Practice and Theory |language=en |volume=264 |pages=90–117 |doi=10.1016/j.dam.2018.11.002 |issn=0166-218X}}</ref>
 === Densest Subgraph ===
-An [[Optimization problem|optimization]] variant of the [[Clique problem|k-Clique problem]] is the Densest k-Subgraph problem (which is a 2-ary [[Constraint satisfaction problem|Constraint Satisfaction problem]]), where the task is to find a subgraph on <math>k</math> vertices with maximum number of edges. It is not hard to obtain a <math>(k-1)</math>-approximation by just picking a [[Matching (graph theory)|matching]] of size <math>k/2</math> in the given input graph, since the maximum number of edges on <math>k</math> vertices is always at most <math>{k \choose 2}= k(k-1)/2</math>. This is also [[Big O notation|asymptotically]] optimal, since under Gap-[[Exponential time hypothesis|ETH]] no <math>k^{1-o(1)}</math>-approximation can be computed in FPT time parameterized by <math>k</math>.<ref>{{Cite journal |last=Dinur |first=Irit |last2=Manurangsi |first2=Pasin |date=2018 |editor-last=Karlin |editor-first=Anna R. |title=ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network |url=http://drops.dagstuhl.de/opus/volltexte/2018/8367 |journal=9th Innovations in Theoretical Computer Science Conference (ITCS 2018) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=94 |pages=36:1–36:20 |doi=10.4230/LIPIcs.ITCS.2018.36 |isbn=978-3-95977-060-6}}</ref>
+An [[Optimization problem|optimization]] variant of the [[Clique problem|k-Clique problem]] is the Densest k-Subgraph problem (which is a 2-ary [[Constraint satisfaction problem|Constraint Satisfaction problem]]), where the task is to find a subgraph on <math>k</math> vertices with maximum number of edges. It is not hard to obtain a <math>(k-1)</math>-approximation by just picking a [[Matching (graph theory)|matching]] of size <math>k/2</math> in the given input graph, since the maximum number of edges on <math>k</math> vertices is always at most <math>{k \choose 2}= k(k-1)/2</math>. This is also [[Big O notation|asymptotically]] optimal, since under Gap-[[Exponential time hypothesis|ETH]] no <math>k^{1-o(1)}</math>-approximation can be computed in FPT time parameterized by <math>k</math>.<ref>{{Cite journal |last1=Dinur |first1=Irit |last2=Manurangsi |first2=Pasin |date=2018 |editor-last=Karlin |editor-first=Anna R. |title=ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network |url=http://drops.dagstuhl.de/opus/volltexte/2018/8367 |journal=9th Innovations in Theoretical Computer Science Conference (ITCS 2018) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=94 |pages=36:1–36:20 |doi=10.4230/LIPIcs.ITCS.2018.36 |isbn=978-3-95977-060-6|s2cid=4681120 }}</ref>
 === Dominating Set ===
-For the [[Dominating set problem|Dominating Set problem]] it is W[1]-hard to compute any <math>g(k)</math>-approximation in <math>f(k)n^{O(1)}</math> time for any functions <math>g</math> and <math>f</math>.<ref>{{Cite journal |last=S. |first=Karthik C. |last2=Laekhanukit |first2=Bundit |last3=Manurangsi |first3=Pasin |date=2018-06-20 |title=On the parameterized complexity of approximating dominating set |url=https://doi.org/10.1145/3188745.3188896 |journal=Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |series=STOC 2018 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=1283–1296 |doi=10.1145/3188745.3188896 |isbn=978-1-4503-5559-9}}</ref>
+For the [[Dominating set problem|Dominating Set problem]] it is W[1]-hard to compute any <math>g(k)</math>-approximation in <math>f(k)n^{O(1)}</math> time for any functions <math>g</math> and <math>f</math>.<ref>{{Cite journal |last1=S. |first1=Karthik C. |last2=Laekhanukit |first2=Bundit |last3=Manurangsi |first3=Pasin |date=2018-06-20 |title=On the parameterized complexity of approximating dominating set |url=https://doi.org/10.1145/3188745.3188896 |journal=Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |series=STOC 2018 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=1283–1296 |doi=10.1145/3188745.3188896 |arxiv=1711.11029 |isbn=978-1-4503-5559-9|s2cid=3170316 }}</ref>
 == Approximate kernelization ==
-[[Kernelization]] is a technique used in [[Parameterized complexity|fixed-parameter tractability]] to pre-process an instance of an [[NP-hardness|NP-hard]] problem in order to remove "easy parts" and reveal the NP-hard core of the instance. A kernelization algorithm takes an instance <math>I</math> and a parameter <math>k</math>, and returns a new instance <math>I'</math> with parameter <math>k'</math> such that the size of <math>I'</math> and <math>k'</math> is bounded as a function of the input parameter <math>k</math>, and the algorithm runs in polynomial time. An '''<math>\alpha</math>-approximate kernelization algorithm''' is a variation of this technique that is used in parameterized approximation algorithms. It returns a kernel <math>I'</math> such that any <math>\beta</math>-approximation in <math>I'</math> can be converted into an <math>\alpha\beta</math>-approximation to the input instance <math>I</math> in polynomial time. This notion was introduced by Lokshtanov et al.,<ref name=":0">{{Cite journal |last=Lokshtanov |first=Daniel |last2=Panolan |first2=Fahad |last3=Ramanujan |first3=M. S. |last4=Saurabh |first4=Saket |date=2017-06-19 |title=Lossy kernelization |url=https://doi.org/10.1145/3055399.3055456 |journal=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |series=STOC 2017 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=224–237 |doi=10.1145/3055399.3055456 |isbn=978-1-4503-4528-6}}</ref> but there are other related notions in the literature such as Turing kernels<ref>{{Cite journal |last=Hermelin |first=Danny |last2=Kratsch |first2=Stefan |last3=Sołtys |first3=Karolina |last4=Wahlström |first4=Magnus |last5=Wu |first5=Xi |date=2015-03-01 |title=A Completeness Theory for Polynomial (Turing) Kernelization |url=https://doi.org/10.1007/s00453-014-9910-8 |journal=Algorithmica |language=en |volume=71 |issue=3 |pages=702–730 |doi=10.1007/s00453-014-9910-8 |issn=1432-0541}}</ref> and '''<math>\alpha</math>'''-fidelity kernelization.<ref>{{Cite journal |last=Fellows |first=Michael R. |last2=Kulik |first2=Ariel |last3=Rosamond |first3=Frances |last4=Shachnai |first4=Hadas |author4-link= Hadas Shachnai |date=2018-05-01 |title=Parameterized approximation via fidelity preserving transformations |url=https://www.sciencedirect.com/science/article/pii/S0022000017302222 |journal=Journal of Computer and System Sciences |language=en |volume=93 |pages=30–40 |doi=10.1016/j.jcss.2017.11.001 |issn=0022-0000}}</ref>
+[[Kernelization]] is a technique used in [[Parameterized complexity|fixed-parameter tractability]] to pre-process an instance of an [[NP-hardness|NP-hard]] problem in order to remove "easy parts" and reveal the NP-hard core of the instance. A kernelization algorithm takes an instance <math>I</math> and a parameter <math>k</math>, and returns a new instance <math>I'</math> with parameter <math>k'</math> such that the size of <math>I'</math> and <math>k'</math> is bounded as a function of the input parameter <math>k</math>, and the algorithm runs in polynomial time. An '''<math>\alpha</math>-approximate kernelization algorithm''' is a variation of this technique that is used in parameterized approximation algorithms. It returns a kernel <math>I'</math> such that any <math>\beta</math>-approximation in <math>I'</math> can be converted into an <math>\alpha\beta</math>-approximation to the input instance <math>I</math> in polynomial time. This notion was introduced by Lokshtanov et al.,<ref name=":0">{{Cite journal |last1=Lokshtanov |first1=Daniel |last2=Panolan |first2=Fahad |last3=Ramanujan |first3=M. S. |last4=Saurabh |first4=Saket |date=2017-06-19 |title=Lossy kernelization |url=https://doi.org/10.1145/3055399.3055456 |journal=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |series=STOC 2017 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=224–237 |doi=10.1145/3055399.3055456 |isbn=978-1-4503-4528-6|s2cid=14599219 }}</ref> but there are other related notions in the literature such as Turing kernels<ref>{{Cite journal |last1=Hermelin |first1=Danny |last2=Kratsch |first2=Stefan |last3=Sołtys |first3=Karolina |last4=Wahlström |first4=Magnus |last5=Wu |first5=Xi |date=2015-03-01 |title=A Completeness Theory for Polynomial (Turing) Kernelization |url=https://doi.org/10.1007/s00453-014-9910-8 |journal=Algorithmica |language=en |volume=71 |issue=3 |pages=702–730 |doi=10.1007/s00453-014-9910-8 |s2cid=253973283 |issn=1432-0541}}</ref> and '''<math>\alpha</math>'''-fidelity kernelization.<ref>{{Cite journal |last1=Fellows |first1=Michael R. |last2=Kulik |first2=Ariel |last3=Rosamond |first3=Frances |last4=Shachnai |first4=Hadas |author4-link= Hadas Shachnai |date=2018-05-01 |title=Parameterized approximation via fidelity preserving transformations |url=https://www.sciencedirect.com/science/article/pii/S0022000017302222 |journal=Journal of Computer and System Sciences |language=en |volume=93 |pages=30–40 |doi=10.1016/j.jcss.2017.11.001 |issn=0022-0000}}</ref>
 As for regular (non-approximate) 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 [[Kernelization#Kernelizability and fixed-parameter tractability are equivalent|the one for regular kernels]].<ref name=":0" /> 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 '''<math>\alpha</math>'''-approximate kernelization algorithm that computes a polynomial-sized kernel and for which '''<math>\alpha</math>''' can be set to <math>1+\varepsilon</math> for any <math>\varepsilon>0</math>.