Parameterized approximation algorithm - Revision history

Ira Leviton: Fixed a reference. Please see Category:CS1 errors: dates.

2025-06-02T18:31:29Z

Fixed a reference. Please see Category:CS1 errors: dates.

← Previous revision		Revision as of 18:31, 2 June 2025
Line 16:		Line 16:
	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>\mathsf{P}\neq \mathsf{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 \|arxiv=1705.03581 }}</ref> It is also W[1]-hard parameterized by the number {{mvar\|k}} of required components.<ref>{{Cite journal \|last1=G. Downey \|first1=Rodney \|last2=Estivill-Castro \|first2=Vladimir \|last3=Fellows \|first3=Michael \|last4=Prieto \|first4=Elena \|author4-link=Elena Prieto-Rodriguez\|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 \|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\|doi-access=free \|hdl=10230/36518 \|hdl-access=free }}</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>		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>\mathsf{P}\neq \mathsf{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 \|arxiv=1705.03581 }}</ref> It is also W[1]-hard parameterized by the number {{mvar\|k}} of required components.<ref>{{Cite journal \|last1=G. Downey \|first1=Rodney \|last2=Estivill-Castro \|first2=Vladimir \|last3=Fellows \|first3=Michael \|last4=Prieto \|first4=Elena \|author4-link=Elena Prieto-Rodriguez\|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 \|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\|doi-access=free \|hdl=10230/36518 \|hdl-access=free }}</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>

	=== Travelling Salesman ~~(TSP)~~ ===		=== Travelling Salesman ===
	The [[Travelling Salesman problem]] is [[APX-hard]] and [[Parameterized complexity\|paraNP-hard]] parameterized by the [[Doubling space\|doubling dimension]] (as it is [[NP-hardness\|NP-hard]] in the [[Euclidean plane]]). However, an EPAS exists parameterized by the [[Doubling space\|doubling dimension]], and even for the more general [[highway dimension]] parameter.<ref>{{Citation \|last=Emil Feldmann \|first=Andreas \|title=Highway Dimension: a Metric View \|date=2025~~-01~~ \|work=Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) \|pages=3267–3276 \|url=https://epubs.siam.org/doi/10.1137/1.9781611978322.104 \|access-date=2025-06-02 \|series=Proceedings \|publisher=Society for Industrial and Applied Mathematics \|doi=10.1137/1.9781611978322.104 \|last2=Filtser \|first2=Arnold}}</ref>		The [[Travelling Salesman problem]] is [[APX-hard]] and [[Parameterized complexity\|paraNP-hard]] parameterized by the [[Doubling space\|doubling dimension]] (as it is [[NP-hardness\|NP-hard]] in the [[Euclidean plane]]). However, an EPAS exists parameterized by the [[Doubling space\|doubling dimension]], and even for the more general [[highway dimension]] parameter.<ref>{{Citation \|last=Emil Feldmann \|first=Andreas \|title=Highway Dimension: a Metric View \|date=January 2025 \|work=Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) \|pages=3267–3276 \|url=https://epubs.siam.org/doi/10.1137/1.9781611978322.104 \|access-date=2025-06-02 \|series=Proceedings \|publisher=Society for Industrial and Applied Mathematics \|doi=10.1137/1.9781611978322.104 \|last2=Filtser \|first2=Arnold}}</ref>

	=== Steiner Tree ===		=== Steiner Tree ===

Astenosfear: added new results on TSP

2025-06-02T12:55:14Z

added new results on TSP

Show changes

Darconis: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-03-15T03:37:02Z

Link suggestions feature: 3 links added.

← Previous revision		Revision as of 03:37, 15 March 2025
Line 1:		Line 1:
	{{Short description\|Type of algorithm}}		{{Short description\|Type of algorithm}}
	{{Use mdy dates\|cs1-dates=ly\|date=February 2024}}		{{Use mdy dates\|cs1-dates=ly\|date=February 2024}}
	A '''parameterized approximation algorithm''' is a type of [[algorithm]] that aims to find approximate solutions to [[NP-hardness\|NP-hard]] [[optimization problem]]s 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 algorithm]]s and [[Parameterized complexity\|fixed-parameter tractability.]]		A '''parameterized approximation algorithm''' is a type of [[algorithm]] that aims to find approximate solutions to [[NP-hardness\|NP-hard]] [[optimization problem]]s in [[Time complexity\|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 algorithm]]s and [[Parameterized complexity\|fixed-parameter tractability.]]

	In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor {{mvar\|α}} away from the optimal solution, known as an {{mvar\|α}}-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 {{mvar\|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 <math>f(k)n^{O(1)}</math> time, where <math>f(k)</math> is a function independent of the input size {{mvar\|n}}.		In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor {{mvar\|α}} away from the optimal solution, known as an {{mvar\|α}}-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 {{mvar\|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 <math>f(k)n^{O(1)}</math> time, where <math>f(k)</math> is a function independent of the input size {{mvar\|n}}.
Line 56:		Line 56:
	[[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 {{mvar\|I}} and a parameter {{mvar\|k}}, 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 {{mvar\|k}}, and the algorithm runs in polynomial time. An '''{{mvar\|α}}-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 {{mvar\|β}}-approximation in <math>I'</math> can be converted into an {{mvar\|αβ}}-approximation to the input instance {{mvar\|I}} in polynomial time. This notion was introduced by Lokshtanov et al.,<ref name=":0">{{Cite book \|last1=Lokshtanov \|first1=Daniel \|last2=Panolan \|first2=Fahad \|last3=Ramanujan \|first3=M. S. \|last4=Saurabh \|first4=Saket \|title=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing \|chapter=Lossy kernelization \|date=2017-06-19 \|chapter-url=https://doi.org/10.1145/3055399.3055456 \|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 \|url=http://wrap.warwick.ac.uk/113741/1/WRAP-Lossy-Kernelization-Ramanujan-2019.pdf }}</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 '''{{mvar\|α}}'''-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>		[[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 {{mvar\|I}} and a parameter {{mvar\|k}}, 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 {{mvar\|k}}, and the algorithm runs in polynomial time. An '''{{mvar\|α}}-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 {{mvar\|β}}-approximation in <math>I'</math> can be converted into an {{mvar\|αβ}}-approximation to the input instance {{mvar\|I}} in polynomial time. This notion was introduced by Lokshtanov et al.,<ref name=":0">{{Cite book \|last1=Lokshtanov \|first1=Daniel \|last2=Panolan \|first2=Fahad \|last3=Ramanujan \|first3=M. S. \|last4=Saurabh \|first4=Saket \|title=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing \|chapter=Lossy kernelization \|date=2017-06-19 \|chapter-url=https://doi.org/10.1145/3055399.3055456 \|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 \|url=http://wrap.warwick.ac.uk/113741/1/WRAP-Lossy-Kernelization-Ramanujan-2019.pdf }}</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 '''{{mvar\|α}}'''-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 '''{{mvar\|α}}'''-approximate kernelization algorithm that computes a polynomial-sized kernel and for which '''{{mvar\|α}}''' can be set to <math>1+\varepsilon</math> for any <math>\varepsilon>0</math>.		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 '''{{mvar\|α}}'''-approximate kernelization algorithm that computes a polynomial-sized kernel and for which '''{{mvar\|α}}''' can be set to <math>1+\varepsilon</math> for any <math>\varepsilon>0</math>.

	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 <math>\textsf{NP}\subseteq \textsf{coNP/poly}</math>), but a PSAKS exists.<ref name=":0" /> Similarly, the Steiner Tree problem is FPT parameterized by the number of terminals, does not admit a polynomial sized kernel (unless <math>\textsf{NP}\subseteq \textsf{coNP/poly}</math>), but a PSAKS exists.<ref name=":0" /> 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.<ref name=":5" />		For example, while the Connected [[Vertex cover\|Vertex Cover]] problem is FPT parameterized by the solution size, it does not admit a (regular) polynomial sized kernel (unless <math>\textsf{NP}\subseteq \textsf{coNP/poly}</math>), but a PSAKS exists.<ref name=":0" /> Similarly, the Steiner Tree problem is FPT parameterized by the number of terminals, does not admit a polynomial sized kernel (unless <math>\textsf{NP}\subseteq \textsf{coNP/poly}</math>), but a PSAKS exists.<ref name=":0" /> 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.<ref name=":5" />

	== Talks on parameterized approximations ==		== Talks on parameterized approximations ==

Citation bot: Altered title. Add: series, doi-access. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 951/1051

2024-07-29T12:49:34Z

Altered title. Add: series, doi-access. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 951/1051

← Previous revision		Revision as of 12:49, 29 July 2024
Line 32:		Line 32:
	\| title = 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8–12, 2024, Tallinn, Estonia		\| title = 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8–12, 2024, Tallinn, Estonia
	\| volume = 297		\| volume = 297
	\| year = 2024~~}}</ref>~~		\| year = 2024\| doi-access = free
			}}</ref>

	=== Strongly-connected Steiner subgraph ===		=== Strongly-connected Steiner subgraph ===
Line 38:		Line 39:

	=== ''k''-median and ''k''-means ===		=== ''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 {{mvar\|k}} 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 {{mvar\|f}}, 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.		For the well-studied metric clustering problems of [[K-median problem\|''k''-median]] and [[K-means clustering\|''k''-means]] parameterized by the number {{mvar\|k}} 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 {{mvar\|f}}, 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 \|doi-access=free \|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 {{mvar\|d}},<ref>{{cite conference \|last1=Kolliopoulos \|first1=Stavros G. \|contribution=A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem \|date=1999 \|title=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 \|last2=Rao \|first2=Satish}}</ref><ref>{{cite conference \|last=Cohen-Addad \|first=Vincent \|contribution=A Fast Approximation Scheme for Low-Dimensional k-Means \|date=2018 \|title=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\|arxiv=1708.07381 }}</ref> and also an EPAS parameterized by {{mvar\|k}}.<ref>{{Cite book \|last1=Feldman \|first1=Dan \|last2=Monemizadeh \|first2=Morteza \|last3=Sohler \|first3=Christian \|title=Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 \|chapter=A PTAS for k-means clustering based on weak coresets \|date=2007-06-06 \|chapter-url=https://doi.org/10.1145/1247069.1247072 \|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 book \|last1=Feldman \|first1=Dan \|last2=Langberg \|first2=Michael \|title=Proceedings of the forty-third annual ACM symposium on Theory of computing \|chapter=A unified framework for approximating and clustering data \|date=2011-06-06 \|chapter-url=https://doi.org/10.1145/1993636.1993712 \|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>		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 {{mvar\|d}},<ref>{{cite conference \|last1=Kolliopoulos \|first1=Stavros G. \|contribution=A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem \|date=1999 \|title=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 \|last2=Rao \|first2=Satish\|series=Lecture Notes in Computer Science }}</ref><ref>{{cite conference \|last=Cohen-Addad \|first=Vincent \|contribution=A Fast Approximation Scheme for Low-Dimensional k-Means \|date=2018 \|title=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\|arxiv=1708.07381 }}</ref> and also an EPAS parameterized by {{mvar\|k}}.<ref>{{Cite book \|last1=Feldman \|first1=Dan \|last2=Monemizadeh \|first2=Morteza \|last3=Sohler \|first3=Christian \|title=Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 \|chapter=A PTAS for k-means clustering based on weak coresets \|date=2007-06-06 \|chapter-url=https://doi.org/10.1145/1247069.1247072 \|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 book \|last1=Feldman \|first1=Dan \|last2=Langberg \|first2=Michael \|title=Proceedings of the forty-third annual ACM symposium on Theory of computing \|chapter=A unified framework for approximating and clustering data \|date=2011-06-06 \|chapter-url=https://doi.org/10.1145/1993636.1993712 \|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 ===		=== ''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 {{mvar\|k}} 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 book \|last1=Feder \|first1=Tomás \|last2=Greene \|first2=Daniel \|title=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 \|chapter=Optimal algorithms for approximate clustering \|date=1988-01-01 \|chapter-url=https://doi.org/10.1145/62212.62255 \|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]]s when simultaneously parameterizing it by the number {{mvar\|k}} 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\|arxiv=1802.08563 }}</ref> However, when combining {{mvar\|k}} with the doubling dimension an EPAS exists,<ref name=":3" /> and the same is true when combining {{mvar\|k}} 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 conference \|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 \|contribution=Generalized {{mvar\|k}}-Center: Distinguishing Doubling and Highway Dimension \|title=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\|arxiv=1704.08868 }}</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 {{mvar\|k}} 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 book \|last1=Feder \|first1=Tomás \|last2=Greene \|first2=Daniel \|title=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 \|chapter=Optimal algorithms for approximate clustering \|date=1988-01-01 \|chapter-url=https://doi.org/10.1145/62212.62255 \|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]]s when simultaneously parameterizing it by the number {{mvar\|k}} 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\|arxiv=1802.08563 }}</ref> However, when combining {{mvar\|k}} with the doubling dimension an EPAS exists,<ref name=":3" /> and the same is true when combining {{mvar\|k}} 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 \|doi-access=free \|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 conference \|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 \|contribution=Generalized {{mvar\|k}}-Center: Distinguishing Doubling and Highway Dimension \|title=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\|arxiv=1704.08868 }}</ref>

	=== Densest subgraph ===		=== 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 {{mvar\|k}} 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 {{mvar\|k}} 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 {{mvar\|k}}.<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>		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 {{mvar\|k}} 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 {{mvar\|k}} 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 {{mvar\|k}}.<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 \|doi-access=free \|isbn=978-3-95977-060-6\|s2cid=4681120 }}</ref>

	=== Dominating set ===		=== Dominating set ===

David Eppstein: /* Steiner Tree */ fix another bad reference

2024-07-24T07:21:40Z

Steiner Tree: fix another bad reference

@@ Line 17: / Line 17: @@
 === Steiner Tree ===
-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 {{mvar|k}} 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|arxiv=1710.00668 }}</ref> The more general Steiner Forest problem is NP-hard on graphs of treewidth 3. However, on graphs of [[treewidth]] {{mvar|t}} an EPAS can compute a <math>(1+\varepsilon)</math>-approximation in <math>2^{O(\frac{t^2}{\varepsilon}\log \frac{t}{\varepsilon})}n^{O(1)}</math> time.<ref>{{Cite journal |last=Feldmann |first=Andreas Emil |last2=Lampis |first2=Michael |date=2024 |others=Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson |title=Parameterized Algorithms for Steiner Forest in Bounded Width Graphs |url=https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.61 |language=en |pages=20 pages, 843074 bytes |doi=10.4230/LIPICS.ICALP.2024.61 |issn=1868-8969}}</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 {{mvar|k}} 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|arxiv=1710.00668 }}</ref> The more general Steiner Forest problem is NP-hard on graphs of treewidth 3. However, on graphs of [[treewidth]] {{mvar|t}} an EPAS can compute a <math>(1+\varepsilon)</math>-approximation in <math>2^{O(\frac{t^2}{\varepsilon}\log \frac{t}{\varepsilon})}n^{O(1)}</math> time.<ref>{{cite conference
 === Strongly-connected Steiner subgraph ===

143.167.103.122: /* Steiner Tree */ EPAS for Steiner Forest on graphs of bounded treewidth

2024-07-22T15:08:19Z

Steiner Tree: EPAS for Steiner Forest on graphs of bounded treewidth

← Previous revision		Revision as of 15:08, 22 July 2024
Line 17:		Line 17:

	=== Steiner Tree ===		=== Steiner Tree ===
	The [[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 {{mvar\|k}} 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\|arxiv=1710.00668 }}</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 {{mvar\|k}} 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\|arxiv=1710.00668 }}</ref> The more general Steiner Forest problem is NP-hard on graphs of treewidth 3. However, on graphs of [[treewidth]] {{mvar\|t}} an EPAS can compute a <math>(1+\varepsilon)</math>-approximation in <math>2^{O(\frac{t^2}{\varepsilon}\log \frac{t}{\varepsilon})}n^{O(1)}</math> time.<ref>{{Cite journal \|last=Feldmann \|first=Andreas Emil \|last2=Lampis \|first2=Michael \|date=2024 \|others=Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson \|title=Parameterized Algorithms for Steiner Forest in Bounded Width Graphs \|url=https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.61 \|language=en \|pages=20 pages, 843074 bytes \|doi=10.4230/LIPICS.ICALP.2024.61 \|issn=1868-8969}}</ref>

	=== Strongly-connected Steiner subgraph ===		=== Strongly-connected Steiner subgraph ===

David Eppstein: Elena Prieto-Rodriguez

2024-07-18T05:41:32Z

Elena Prieto-Rodriguez

← Previous revision		Revision as of 05:41, 18 July 2024
Line 14:		Line 14:

	=== ''k''-cut ===		=== ''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>\mathsf{P}\neq \mathsf{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 \|arxiv=1705.03581 }}</ref> It is also W[1]-hard parameterized by the number {{mvar\|k}} 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 \|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\|doi-access=free \|hdl=10230/36518 \|hdl-access=free }}</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>		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>\mathsf{P}\neq \mathsf{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 \|arxiv=1705.03581 }}</ref> It is also W[1]-hard parameterized by the number {{mvar\|k}} of required components.<ref>{{Cite journal \|last1=G. Downey \|first1=Rodney \|last2=Estivill-Castro \|first2=Vladimir \|last3=Fellows \|first3=Michael \|last4=Prieto \|first4=Elena \|author4-link=Elena Prieto-Rodriguez\|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 \|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\|doi-access=free \|hdl=10230/36518 \|hdl-access=free }}</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 ===		=== Steiner Tree ===

Cedar101: sans-serif for complexity class

2024-06-21T06:31:16Z

sans-serif for complexity class

Show changes

David Eppstein: fix broken citation; use cs1

2024-02-06T07:39:40Z

fix broken citation; use cs1

← Previous revision		Revision as of 07:39, 6 February 2024
Line 1:		Line 1:
	{{Short description\|Type of algorithm}}		{{Short description\|Type of algorithm}}
			{{Use mdy dates\|cs1-dates=ly\|date=February 2024}}

	A '''parameterized approximation algorithm''' is a type of [[algorithm]] that aims to find approximate solutions to [[NP-hardness\|NP-hard]] [[optimization problem]]s 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 algorithm]]s and [[Parameterized complexity\|fixed-parameter tractability.]]		A '''parameterized approximation algorithm''' is a type of [[algorithm]] that aims to find approximate solutions to [[NP-hardness\|NP-hard]] [[optimization problem]]s 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 algorithm]]s and [[Parameterized complexity\|fixed-parameter tractability.]]

Line 20:		Line 20:

	=== Strongly-connected Steiner subgraph ===		=== 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 \|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 book \|last1=Halperin \|first1=Eran \|last2=Krauthgamer \|first2=Robert \|title=Proceedings of the thirty-fifth annual ACM symposium on Theory of computing \|chapter=Polylogarithmic inapproximability \|date=2003-06-09 \|chapter-url=https://doi.org/10.1145/780542.780628 \|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 ~~book~~ \|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\|arxiv=1707.06499 }}</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 book \|last1=Halperin \|first1=Eran \|last2=Krauthgamer \|first2=Robert \|title=Proceedings of the thirty-fifth annual ACM symposium on Theory of computing \|chapter=Polylogarithmic inapproximability \|date=2003-06-09 \|chapter-url=https://doi.org/10.1145/780542.780628 \|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 conference \|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 \|contribution=Fixed-Parameter and Approximation Algorithms: A New Look \|title=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\|arxiv=1707.06499 }}</ref>

	=== ''k''-median and ''k''-means ===		=== ''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 \|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.		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~~ \|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~~\|arxiv=1708.07381 }}</ref> and also an EPAS parameterized by <math>k</math>.<ref>{{Cite book \|last1=Feldman \|first1=Dan \|last2=Monemizadeh \|first2=Morteza \|last3=Sohler \|first3=Christian \|title=Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 \|chapter=A PTAS for k-means clustering based on weak coresets \|date=2007-06-06 \|chapter-url=https://doi.org/10.1145/1247069.1247072 \|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 book \|last1=Feldman \|first1=Dan \|last2=Langberg \|first2=Michael \|title=Proceedings of the forty-third annual ACM symposium on Theory of computing \|chapter=A unified framework for approximating and clustering data \|date=2011-06-06 \|chapter-url=https://doi.org/10.1145/1993636.1993712 \|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>		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>{{cite conference \|last1=Kolliopoulos \|first1=Stavros G. \|contribution=A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem \|date=1999 \|title=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 \|last2=Rao \|first2=Satish}}</ref><ref>{{cite conference \|last=Cohen-Addad \|first=Vincent \|contribution=A Fast Approximation Scheme for Low-Dimensional k-Means \|date=2018 \|title=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\|arxiv=1708.07381 }}</ref> and also an EPAS parameterized by <math>k</math>.<ref>{{Cite book \|last1=Feldman \|first1=Dan \|last2=Monemizadeh \|first2=Morteza \|last3=Sohler \|first3=Christian \|title=Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 \|chapter=A PTAS for k-means clustering based on weak coresets \|date=2007-06-06 \|chapter-url=https://doi.org/10.1145/1247069.1247072 \|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 book \|last1=Feldman \|first1=Dan \|last2=Langberg \|first2=Michael \|title=Proceedings of the forty-third annual ACM symposium on Theory of computing \|chapter=A unified framework for approximating and clustering data \|date=2011-06-06 \|chapter-url=https://doi.org/10.1145/1993636.1993712 \|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 ===		=== ''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 \|arxiv=1605.02530 \|s2cid=46886829 \|issn=1432-0541}}</ref> the [[Doubling space\|doubling dimension]] (in fact the dimension of a [[Manhattan metric]]),<ref>{{Cite book \|last1=Feder \|first1=Tomás \|last2=Greene \|first2=Daniel \|title=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 \|chapter=Optimal algorithms for approximate clustering \|date=1988-01-01 \|chapter-url=https://doi.org/10.1145/62212.62255 \|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]]s 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\|arxiv=1802.08563 }}</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 ~~book~~ \|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\|arxiv=1704.08868 }}</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 book \|last1=Feder \|first1=Tomás \|last2=Greene \|first2=Daniel \|title=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 \|chapter=Optimal algorithms for approximate clustering \|date=1988-01-01 \|chapter-url=https://doi.org/10.1145/62212.62255 \|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]]s 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\|arxiv=1802.08563 }}</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 conference \|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 \|contribution=Generalized {{mvar\|k}}-Center: Distinguishing Doubling and Highway Dimension \|title=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\|arxiv=1704.08868 }}</ref>

	=== Densest subgraph ===		=== Densest subgraph ===
Line 56:		Line 56:

	== References ==		== References ==
	<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
	{{reflist}}		{{reflist}}

Citation bot: Altered template type. Removed proxy/dead URL that duplicated identifier. Removed parameters. | Use this bot. Report bugs. | Suggested by Abductive | Category:Articles with imported Creative Commons Attribution 4.0 text | #UCB_Category 785/884

2024-01-18T08:46:53Z

Altered template type. Removed proxy/dead URL that duplicated identifier. Removed parameters. | Use this bot. Report bugs. | Suggested by Abductive | Category:Articles with imported Creative Commons Attribution 4.0 text | #UCB_Category 785/884

Show changes

← Previous revision		Revision as of 03:37, 15 March 2025
Line 1:		Line 1:
	{{Short description\|Type of algorithm}}		{{Short description\|Type of algorithm}}
	{{Use mdy dates\|cs1-dates=ly\|date=February 2024}}		{{Use mdy dates\|cs1-dates=ly\|date=February 2024}}
	A '''parameterized approximation algorithm''' is a type of [[algorithm]] that aims to find approximate solutions to [[NP-hardness\|NP-hard]] [[optimization problem]]s 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 algorithm]]s and [[Parameterized complexity\|fixed-parameter tractability.]]		A '''parameterized approximation algorithm''' is a type of [[algorithm]] that aims to find approximate solutions to [[NP-hardness\|NP-hard]] [[optimization problem]]s in [[Time complexity\|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 algorithm]]s and [[Parameterized complexity\|fixed-parameter tractability.]]

	In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor {{mvar\|α}} away from the optimal solution, known as an {{mvar\|α}}-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 {{mvar\|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 <math>f(k)n^{O(1)}</math> time, where <math>f(k)</math> is a function independent of the input size {{mvar\|n}}.		In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor {{mvar\|α}} away from the optimal solution, known as an {{mvar\|α}}-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 {{mvar\|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 <math>f(k)n^{O(1)}</math> time, where <math>f(k)</math> is a function independent of the input size {{mvar\|n}}.
Line 56:		Line 56:
	[[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 {{mvar\|I}} and a parameter {{mvar\|k}}, 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 {{mvar\|k}}, and the algorithm runs in polynomial time. An '''{{mvar\|α}}-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 {{mvar\|β}}-approximation in <math>I'</math> can be converted into an {{mvar\|αβ}}-approximation to the input instance {{mvar\|I}} in polynomial time. This notion was introduced by Lokshtanov et al.,<ref name=":0">{{Cite book \|last1=Lokshtanov \|first1=Daniel \|last2=Panolan \|first2=Fahad \|last3=Ramanujan \|first3=M. S. \|last4=Saurabh \|first4=Saket \|title=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing \|chapter=Lossy kernelization \|date=2017-06-19 \|chapter-url=https://doi.org/10.1145/3055399.3055456 \|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 \|url=http://wrap.warwick.ac.uk/113741/1/WRAP-Lossy-Kernelization-Ramanujan-2019.pdf }}</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 '''{{mvar\|α}}'''-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>		[[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 {{mvar\|I}} and a parameter {{mvar\|k}}, 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 {{mvar\|k}}, and the algorithm runs in polynomial time. An '''{{mvar\|α}}-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 {{mvar\|β}}-approximation in <math>I'</math> can be converted into an {{mvar\|αβ}}-approximation to the input instance {{mvar\|I}} in polynomial time. This notion was introduced by Lokshtanov et al.,<ref name=":0">{{Cite book \|last1=Lokshtanov \|first1=Daniel \|last2=Panolan \|first2=Fahad \|last3=Ramanujan \|first3=M. S. \|last4=Saurabh \|first4=Saket \|title=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing \|chapter=Lossy kernelization \|date=2017-06-19 \|chapter-url=https://doi.org/10.1145/3055399.3055456 \|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 \|url=http://wrap.warwick.ac.uk/113741/1/WRAP-Lossy-Kernelization-Ramanujan-2019.pdf }}</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 '''{{mvar\|α}}'''-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 '''{{mvar\|α}}'''-approximate kernelization algorithm that computes a polynomial-sized kernel and for which '''{{mvar\|α}}''' can be set to <math>1+\varepsilon</math> for any <math>\varepsilon>0</math>.		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 '''{{mvar\|α}}'''-approximate kernelization algorithm that computes a polynomial-sized kernel and for which '''{{mvar\|α}}''' can be set to <math>1+\varepsilon</math> for any <math>\varepsilon>0</math>.

	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 <math>\textsf{NP}\subseteq \textsf{coNP/poly}</math>), but a PSAKS exists.<ref name=":0" /> Similarly, the Steiner Tree problem is FPT parameterized by the number of terminals, does not admit a polynomial sized kernel (unless <math>\textsf{NP}\subseteq \textsf{coNP/poly}</math>), but a PSAKS exists.<ref name=":0" /> 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.<ref name=":5" />		For example, while the Connected [[Vertex cover\|Vertex Cover]] problem is FPT parameterized by the solution size, it does not admit a (regular) polynomial sized kernel (unless <math>\textsf{NP}\subseteq \textsf{coNP/poly}</math>), but a PSAKS exists.<ref name=":0" /> Similarly, the Steiner Tree problem is FPT parameterized by the number of terminals, does not admit a polynomial sized kernel (unless <math>\textsf{NP}\subseteq \textsf{coNP/poly}</math>), but a PSAKS exists.<ref name=":0" /> 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.<ref name=":5" />

	== Talks on parameterized approximations ==		== Talks on parameterized approximations ==