Approximation algorithm - Revision history

2001:638:708:306:290E:2B4C:E37E:90EA: /* Performance guarantees */ fixed a typo

2025-04-25T12:31:44Z

Performance guarantees: fixed a typo

← Previous revision		Revision as of 12:31, 25 April 2025
Line 65:		Line 65:

	== Performance guarantees ==		== Performance guarantees ==
	For some approximation algorithms it is possible to prove certain properties about the approximation of ~~th.e~~ optimum result. For example, a '''''ρ''-approximation algorithm''' ''A'' is defined to be an algorithm for which it has been proven that the value/cost, ''f''(''x''), of the approximate solution ''A''(''x'') to an instance ''x'' will not be more (or less, depending on the situation) than a factor ''ρ'' times the value, OPT, of an optimum solution.		For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a '''''ρ''-approximation algorithm''' ''A'' is defined to be an algorithm for which it has been proven that the value/cost, ''f''(''x''), of the approximate solution ''A''(''x'') to an instance ''x'' will not be more (or less, depending on the situation) than a factor ''ρ'' times the value, OPT, of an optimum solution.

	:<math>\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}</math>		:<math>\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}</math>

Giftlite: /* Introduction */ wlnk

2025-03-24T03:45:50Z

Introduction: wlnk

← Previous revision		Revision as of 03:45, 24 March 2025
Line 7:		Line 7:

	== Introduction ==		== Introduction ==
	A simple example of an approximation algorithm is one for the [[Vertex cover\|minimum vertex cover]] problem, where the goal is to choose the smallest set of vertices such that every edge in the input graph contains at least one chosen vertex. One way to find a vertex cover is to repeat the following process: find an uncovered edge, add both its endpoints to the cover, and remove all edges incident to either vertex from the graph. As any vertex cover of the input graph must use a distinct vertex to cover each edge that was considered in the process (since it forms a [[Matching (graph theory)\|matching]]), the vertex cover produced, therefore, is at most twice as large as the optimal one. In other words, this is a [[constant-factor approximation algorithm]] with an approximation factor of 2. Under the recent [[unique games conjecture]], this factor is even the best possible one.<ref>{{Cite journal\|last1=Khot\|first1=Subhash\|last2=Regev\|first2=Oded\|date=2008-05-01\|title=Vertex cover might be hard to approximate to within 2−ε\|journal=Journal of Computer and System Sciences\|series=Computational Complexity 2003\|volume=74\|issue=3\|pages=335–349\|doi=10.1016/j.jcss.2007.06.019\|doi-access=free}}</ref>		A simple example of an approximation algorithm is one for the [[Vertex cover\|minimum vertex cover]] problem, where the goal is to choose the smallest set of vertices such that every edge in the input graph contains at least one chosen vertex. One way to find a [[vertex cover]] is to repeat the following process: find an uncovered edge, add both its endpoints to the cover, and remove all edges incident to either vertex from the graph. As any vertex cover of the input graph must use a distinct vertex to cover each edge that was considered in the process (since it forms a [[Matching (graph theory)\|matching]]), the vertex cover produced, therefore, is at most twice as large as the optimal one. In other words, this is a [[constant-factor approximation algorithm]] with an approximation factor of 2. Under the recent [[unique games conjecture]], this factor is even the best possible one.<ref>{{Cite journal\|last1=Khot\|first1=Subhash\|last2=Regev\|first2=Oded\|date=2008-05-01\|title=Vertex cover might be hard to approximate to within 2−ε\|journal=Journal of Computer and System Sciences\|series=Computational Complexity 2003\|volume=74\|issue=3\|pages=335–349\|doi=10.1016/j.jcss.2007.06.019\|doi-access=free}}</ref>

	NP-hard problems vary greatly in their approximability; some, such as the [[knapsack problem]], can be approximated within a multiplicative factor <math>1 + \epsilon</math>, for any fixed <math>\epsilon > 0</math>, and therefore produce solutions arbitrarily close to the optimum (such a family of approximation algorithms is called a [[polynomial-time approximation scheme]] or PTAS). Others are impossible to approximate within any constant, or even polynomial, factor unless [[P = NP]], as in the case of the [[Clique problem\|maximum clique problem]]. Therefore, an important benefit of studying approximation algorithms is a fine-grained classification of the difficulty of various NP-hard problems beyond the one afforded by the [[NP-completeness\|theory of NP-completeness]]. In other words, although NP-complete problems may be equivalent (under polynomial-time reductions) to each other from the perspective of exact solutions, the corresponding optimization problems behave very differently from the perspective of approximate solutions.		NP-hard problems vary greatly in their approximability; some, such as the [[knapsack problem]], can be approximated within a multiplicative factor <math>1 + \epsilon</math>, for any fixed <math>\epsilon > 0</math>, and therefore produce solutions arbitrarily close to the optimum (such a family of approximation algorithms is called a [[polynomial-time approximation scheme]] or PTAS). Others are impossible to approximate within any constant, or even polynomial, factor unless [[P = NP]], as in the case of the [[Clique problem\|maximum clique problem]]. Therefore, an important benefit of studying approximation algorithms is a fine-grained classification of the difficulty of various NP-hard problems beyond the one afforded by the [[NP-completeness\|theory of NP-completeness]]. In other words, although NP-complete problems may be equivalent (under polynomial-time reductions) to each other from the perspective of exact solutions, the corresponding optimization problems behave very differently from the perspective of approximate solutions.

132.75.176.232: /* Hardness of approximation */Nvm

2025-01-01T14:34:15Z

Hardness of approximation: Nvm

← Previous revision		Revision as of 14:34, 1 January 2025
Line 28:		Line 28:

	== Hardness of approximation ==		== Hardness of approximation ==
	Approximation algorithms as a research area is closely related to and informed by [[Hardness of approximation\|inapproximability theory]] where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of [[Reduction (complexity)\|reductions]]. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.~~008197~~ unless P = NP, Karpinski, Lampis, Schmied.<ref>{{Cite journal\|last1=Karpinski\|first1=Marek\|last2=Lampis\|first2=Michael\|last3=Schmied\|first3=Richard\|date=2015-12-01\|title=New inapproximability bounds for TSP\|journal=Journal of Computer and System Sciences\|volume=81\|issue=8\|pages=1665–1677\|doi=10.1016/j.jcss.2015.06.003\|arxiv=1303.6437}}</ref> Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5.		Approximation algorithms as a research area is closely related to and informed by [[Hardness of approximation\|inapproximability theory]] where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of [[Reduction (complexity)\|reductions]]. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.008196 unless P = NP, Karpinski, Lampis, Schmied.<ref>{{Cite journal\|last1=Karpinski\|first1=Marek\|last2=Lampis\|first2=Michael\|last3=Schmied\|first3=Richard\|date=2015-12-01\|title=New inapproximability bounds for TSP\|journal=Journal of Computer and System Sciences\|volume=81\|issue=8\|pages=1665–1677\|doi=10.1016/j.jcss.2015.06.003\|arxiv=1303.6437}}</ref> Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5.

	While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)\|Independent Set]]<ref>{{Cite journal\|last1=Feige\|first1=Uriel\|last2=Goldwasser\|first2=Shafi\|last3=Lovász\|first3=Laszlo\|last4=Safra\|first4=Shmuel\|last5=Szegedy\|first5=Mario\|date=March 1996\|title=Interactive Proofs and the Hardness of Approximating Cliques\|journal=J. ACM\|volume=43\|issue=2\|pages=268–292\|doi=10.1145/226643.226652\|issn=0004-5411\|doi-access=free}}</ref> and the famous [[PCP theorem]],<ref>{{Cite journal\|last1=Arora\|first1=Sanjeev\|last2=Safra\|first2=Shmuel\|date=January 1998\|title=Probabilistic Checking of Proofs: A New Characterization of NP\|journal=J. ACM\|volume=45\|issue=1\|pages=70–122\|doi=10.1145/273865.273901\|s2cid=751563\|issn=0004-5411\|doi-access=free}}</ref> that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that [[David S. Johnson\|Johnson's]] 1974 approximation algorithms for [[Maximum satisfiability problem\|Max SAT]], [[Set cover problem\|set cover]], [[Independent set (graph theory)\|independent set]] and [[Graph coloring\|coloring]] all achieve the optimal approximation ratio, assuming P ≠ NP.<ref>{{Cite journal\|last=Johnson\|first=David S.\|date=1974-12-01\|title=Approximation algorithms for combinatorial problems\|journal=Journal of Computer and System Sciences\|volume=9\|issue=3\|pages=256–278\|doi=10.1016/S0022-0000(74)80044-9\|doi-access=free}}</ref>		While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)\|Independent Set]]<ref>{{Cite journal\|last1=Feige\|first1=Uriel\|last2=Goldwasser\|first2=Shafi\|last3=Lovász\|first3=Laszlo\|last4=Safra\|first4=Shmuel\|last5=Szegedy\|first5=Mario\|date=March 1996\|title=Interactive Proofs and the Hardness of Approximating Cliques\|journal=J. ACM\|volume=43\|issue=2\|pages=268–292\|doi=10.1145/226643.226652\|issn=0004-5411\|doi-access=free}}</ref> and the famous [[PCP theorem]],<ref>{{Cite journal\|last1=Arora\|first1=Sanjeev\|last2=Safra\|first2=Shmuel\|date=January 1998\|title=Probabilistic Checking of Proofs: A New Characterization of NP\|journal=J. ACM\|volume=45\|issue=1\|pages=70–122\|doi=10.1145/273865.273901\|s2cid=751563\|issn=0004-5411\|doi-access=free}}</ref> that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that [[David S. Johnson\|Johnson's]] 1974 approximation algorithms for [[Maximum satisfiability problem\|Max SAT]], [[Set cover problem\|set cover]], [[Independent set (graph theory)\|independent set]] and [[Graph coloring\|coloring]] all achieve the optimal approximation ratio, assuming P ≠ NP.<ref>{{Cite journal\|last=Johnson\|first=David S.\|date=1974-12-01\|title=Approximation algorithms for combinatorial problems\|journal=Journal of Computer and System Sciences\|volume=9\|issue=3\|pages=256–278\|doi=10.1016/S0022-0000(74)80044-9\|doi-access=free}}</ref>

132.75.176.232: /* Hardness of approximation */123/122=1.008196721311≈1.008197≈×1.008196

2025-01-01T14:32:59Z

Hardness of approximation: 123/122=1.008196721311≈1.008197≈×1.008196

← Previous revision		Revision as of 14:32, 1 January 2025
Line 28:		Line 28:

	== Hardness of approximation ==		== Hardness of approximation ==
	Approximation algorithms as a research area is closely related to and informed by [[Hardness of approximation\|inapproximability theory]] where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of [[Reduction (complexity)\|reductions]]. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.~~008196~~ unless P = NP, Karpinski, Lampis, Schmied.<ref>{{Cite journal\|last1=Karpinski\|first1=Marek\|last2=Lampis\|first2=Michael\|last3=Schmied\|first3=Richard\|date=2015-12-01\|title=New inapproximability bounds for TSP\|journal=Journal of Computer and System Sciences\|volume=81\|issue=8\|pages=1665–1677\|doi=10.1016/j.jcss.2015.06.003\|arxiv=1303.6437}}</ref> Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5.		Approximation algorithms as a research area is closely related to and informed by [[Hardness of approximation\|inapproximability theory]] where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of [[Reduction (complexity)\|reductions]]. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.008197 unless P = NP, Karpinski, Lampis, Schmied.<ref>{{Cite journal\|last1=Karpinski\|first1=Marek\|last2=Lampis\|first2=Michael\|last3=Schmied\|first3=Richard\|date=2015-12-01\|title=New inapproximability bounds for TSP\|journal=Journal of Computer and System Sciences\|volume=81\|issue=8\|pages=1665–1677\|doi=10.1016/j.jcss.2015.06.003\|arxiv=1303.6437}}</ref> Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5.

	While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)\|Independent Set]]<ref>{{Cite journal\|last1=Feige\|first1=Uriel\|last2=Goldwasser\|first2=Shafi\|last3=Lovász\|first3=Laszlo\|last4=Safra\|first4=Shmuel\|last5=Szegedy\|first5=Mario\|date=March 1996\|title=Interactive Proofs and the Hardness of Approximating Cliques\|journal=J. ACM\|volume=43\|issue=2\|pages=268–292\|doi=10.1145/226643.226652\|issn=0004-5411\|doi-access=free}}</ref> and the famous [[PCP theorem]],<ref>{{Cite journal\|last1=Arora\|first1=Sanjeev\|last2=Safra\|first2=Shmuel\|date=January 1998\|title=Probabilistic Checking of Proofs: A New Characterization of NP\|journal=J. ACM\|volume=45\|issue=1\|pages=70–122\|doi=10.1145/273865.273901\|s2cid=751563\|issn=0004-5411\|doi-access=free}}</ref> that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that [[David S. Johnson\|Johnson's]] 1974 approximation algorithms for [[Maximum satisfiability problem\|Max SAT]], [[Set cover problem\|set cover]], [[Independent set (graph theory)\|independent set]] and [[Graph coloring\|coloring]] all achieve the optimal approximation ratio, assuming P ≠ NP.<ref>{{Cite journal\|last=Johnson\|first=David S.\|date=1974-12-01\|title=Approximation algorithms for combinatorial problems\|journal=Journal of Computer and System Sciences\|volume=9\|issue=3\|pages=256–278\|doi=10.1016/S0022-0000(74)80044-9\|doi-access=free}}</ref>		While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)\|Independent Set]]<ref>{{Cite journal\|last1=Feige\|first1=Uriel\|last2=Goldwasser\|first2=Shafi\|last3=Lovász\|first3=Laszlo\|last4=Safra\|first4=Shmuel\|last5=Szegedy\|first5=Mario\|date=March 1996\|title=Interactive Proofs and the Hardness of Approximating Cliques\|journal=J. ACM\|volume=43\|issue=2\|pages=268–292\|doi=10.1145/226643.226652\|issn=0004-5411\|doi-access=free}}</ref> and the famous [[PCP theorem]],<ref>{{Cite journal\|last1=Arora\|first1=Sanjeev\|last2=Safra\|first2=Shmuel\|date=January 1998\|title=Probabilistic Checking of Proofs: A New Characterization of NP\|journal=J. ACM\|volume=45\|issue=1\|pages=70–122\|doi=10.1145/273865.273901\|s2cid=751563\|issn=0004-5411\|doi-access=free}}</ref> that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that [[David S. Johnson\|Johnson's]] 1974 approximation algorithms for [[Maximum satisfiability problem\|Max SAT]], [[Set cover problem\|set cover]], [[Independent set (graph theory)\|independent set]] and [[Graph coloring\|coloring]] all achieve the optimal approximation ratio, assuming P ≠ NP.<ref>{{Cite journal\|last=Johnson\|first=David S.\|date=1974-12-01\|title=Approximation algorithms for combinatorial problems\|journal=Journal of Computer and System Sciences\|volume=9\|issue=3\|pages=256–278\|doi=10.1016/S0022-0000(74)80044-9\|doi-access=free}}</ref>

5.102.3.156: /* Performingnce guarantees */

2024-06-18T15:02:43Z

Performingnce guarantees

← Previous revision		Revision as of 15:02, 18 June 2024
Line 64:		Line 64:
	The approximation can be proven ''tight'' (''tight approximation'') by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario.		The approximation can be proven ''tight'' (''tight approximation'') by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario.

	== ~~Performingnce~~ guarantees ==		== Performance guarantees ==
	For some approximation algorithms it is possible to prove certain properties about the approximation of th.e optimum result. For example, a '''''ρ''-approximation algorithm''' ''A'' is defined to be an algorithm for which it has been proven that the value/cost, ''f''(''x''), of the approximate solution ''A''(''x'') to an instance ''x'' will not be more (or less, depending on the situation) than a factor ''ρ'' times the value, OPT, of an optimum solution.		For some approximation algorithms it is possible to prove certain properties about the approximation of th.e optimum result. For example, a '''''ρ''-approximation algorithm''' ''A'' is defined to be an algorithm for which it has been proven that the value/cost, ''f''(''x''), of the approximate solution ''A''(''x'') to an instance ''x'' will not be more (or less, depending on the situation) than a factor ''ρ'' times the value, OPT, of an optimum solution.

5.102.3.156: /* Structure of approximation algorithms */

2024-06-18T15:02:27Z

Structure of approximation algorithms

← Previous revision		Revision as of 15:02, 18 June 2024
Line 59:		Line 59:
	Specifically, having <math>A_{\Pi}(i) \in S_i</math>, the algorithm has an '''approximation factor''' (or '''approximation ratio''') of <math>\rho(n)</math> if <math>\forall i \in I \ s.t. \|i\| = n</math>, we have:		Specifically, having <math>A_{\Pi}(i) \in S_i</math>, the algorithm has an '''approximation factor''' (or '''approximation ratio''') of <math>\rho(n)</math> if <math>\forall i \in I \ s.t. \|i\| = n</math>, we have:

	* for a ''minimization'' problem: <math>\frac{c(A_{\Pi}(i)}{c(s^*(i))}\leq\rho(n)</math>, which in turn means the solution taken by the algorithm divided by the optimal solution achieves a ratio of <math>\rho(n)</math>;		* for a ''minimization'' problem: <math>\frac{c(A_{\Pi}(i))}{c(s^*(i))}\leq\rho(n)</math>, which in turn means the solution taken by the algorithm divided by the optimal solution achieves a ratio of <math>\rho(n)</math>;
	* for a ''maximization'' problem: <math>\frac{c(s^*(i))}{c(A_{\Pi}(i)}\leq\rho(n)</math>, which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of <math>\rho(n)</math>;		* for a ''maximization'' problem: <math>\frac{c(s^*(i))}{c(A_{\Pi}(i))}\leq\rho(n)</math>, which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of <math>\rho(n)</math>;

	The approximation can be proven ''tight'' (''tight approximation'') by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario.		The approximation can be proven ''tight'' (''tight approximation'') by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario.

5.102.3.156: /* Structure of approximation algorithms */

2024-06-18T15:01:44Z

Structure of approximation algorithms

← Previous revision		Revision as of 15:01, 18 June 2024
Line 62:		Line 62:
	* for a ''maximization'' problem: <math>\frac{c(s^*(i))}{c(A_{\Pi}(i)}\leq\rho(n)</math>, which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of <math>\rho(n)</math>;		* for a ''maximization'' problem: <math>\frac{c(s^*(i))}{c(A_{\Pi}(i)}\leq\rho(n)</math>, which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of <math>\rho(n)</math>;

	The approximation can be proven ''tight'' (''tight approximation'') by d		The approximation can be proven ''tight'' (''tight approximation'') by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario.

	== Performingnce guarantees ==		== Performingnce guarantees ==

5.102.3.156: /* Performance guarantees */

2024-06-18T15:01:02Z

Performance guarantees

← Previous revision		Revision as of 15:01, 18 June 2024
Line 38:		Line 38:
	In other cases, even if the initial results are of purely theoretical interest, over time, with an improved understanding, the algorithms may be refined to become more practical. One such example is the initial PTAS for [[Euclidean traveling salesman problem\|Euclidean TSP]] by [[Sanjeev Arora]] (and independently by [[Joseph S. B. Mitchell\|Joseph Mitchell]]) which had a prohibitive running time of <math>n^{O(1/\epsilon)}</math> for a <math>1+\epsilon</math> approximation.<ref>{{Cite book\|last=Arora\|first=S.\|title=Proceedings of 37th Conference on Foundations of Computer Science \|chapter=Polynomial time approximation schemes for Euclidean TSP and other geometric problems \|date=October 1996\|pages=2–11\|doi=10.1109/SFCS.1996.548458\|isbn=978-0-8186-7594-2\|citeseerx=10.1.1.32.3376\|s2cid=1499391}}</ref> Yet, within a year these ideas were incorporated into a near-linear time <math>O(n\log n)</math> algorithm for any constant <math>\epsilon > 0</math>.<ref>{{Cite book\|last=Arora\|first=S.\|title=Proceedings 38th Annual Symposium on Foundations of Computer Science \|date=October 1997\|chapter=Nearly linear time approximation schemes for Euclidean TSP and other geometric problems\|pages=554–563\|doi=10.1109/SFCS.1997.646145\|isbn=978-0-8186-8197-4\|s2cid=10656723}}</ref>		In other cases, even if the initial results are of purely theoretical interest, over time, with an improved understanding, the algorithms may be refined to become more practical. One such example is the initial PTAS for [[Euclidean traveling salesman problem\|Euclidean TSP]] by [[Sanjeev Arora]] (and independently by [[Joseph S. B. Mitchell\|Joseph Mitchell]]) which had a prohibitive running time of <math>n^{O(1/\epsilon)}</math> for a <math>1+\epsilon</math> approximation.<ref>{{Cite book\|last=Arora\|first=S.\|title=Proceedings of 37th Conference on Foundations of Computer Science \|chapter=Polynomial time approximation schemes for Euclidean TSP and other geometric problems \|date=October 1996\|pages=2–11\|doi=10.1109/SFCS.1996.548458\|isbn=978-0-8186-7594-2\|citeseerx=10.1.1.32.3376\|s2cid=1499391}}</ref> Yet, within a year these ideas were incorporated into a near-linear time <math>O(n\log n)</math> algorithm for any constant <math>\epsilon > 0</math>.<ref>{{Cite book\|last=Arora\|first=S.\|title=Proceedings 38th Annual Symposium on Foundations of Computer Science \|date=October 1997\|chapter=Nearly linear time approximation schemes for Euclidean TSP and other geometric problems\|pages=554–563\|doi=10.1109/SFCS.1997.646145\|isbn=978-0-8186-8197-4\|s2cid=10656723}}</ref>

			== Structure of approximation algorithms ==
⚫	== ~~Performance~~ guarantees ==
			Given an optimization problem:
⚫	For some approximation algorithms it is possible to prove certain properties about the approximation of ~~the~~ optimum result. For example, a '''''ρ''-approximation algorithm''' ''A'' is defined to be an algorithm for which it has been proven that the value/cost, ''f''(''x''), of the approximate solution ''A''(''x'') to an instance ''x'' will not be more (or less, depending on the situation) than a factor ''ρ'' times the value, OPT, of an optimum solution.

			<math>\Pi: I \times S</math>

			where <math>\Pi</math> is an approximation problem, <math>I</math> the set of inputs and <math>S</math> the set of solutions, we can define the cost function:

			<math>c: S \rightarrow \mathbb{R}^+</math>

			and the set of feasible solutions:

			<math>\forall i \in I, S(i) = {s \in S: i\Pi_s}</math>

			finding the best solution <math>s^*</math> for a maximization or a minimization problem:

			<math>s^* \in S(i)</math>, <math>c(s^*) = min/max \ c(S(i))</math>

			Given a feasible solution <math>s \in S(i)</math>, with <math>s \neq s^*</math>, we would want a guarantee of the quality of the solution, which is a performance to be guaranteed (approximation factor).

			Specifically, having <math>A_{\Pi}(i) \in S_i</math>, the algorithm has an '''approximation factor''' (or '''approximation ratio''') of <math>\rho(n)</math> if <math>\forall i \in I \ s.t. \|i\| = n</math>, we have:

			* for a ''minimization'' problem: <math>\frac{c(A_{\Pi}(i)}{c(s^*(i))}\leq\rho(n)</math>, which in turn means the solution taken by the algorithm divided by the optimal solution achieves a ratio of <math>\rho(n)</math>;
			* for a ''maximization'' problem: <math>\frac{c(s^*(i))}{c(A_{\Pi}(i)}\leq\rho(n)</math>, which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of <math>\rho(n)</math>;

			The approximation can be proven ''tight'' (''tight approximation'') by d

		⚫	== Performingnce guarantees ==
		⚫	For some approximation algorithms it is possible to prove certain properties about the approximation of th.e optimum result. For example, a '''''ρ''-approximation algorithm''' ''A'' is defined to be an algorithm for which it has been proven that the value/cost, ''f''(''x''), of the approximate solution ''A''(''x'') to an instance ''x'' will not be more (or less, depending on the situation) than a factor ''ρ'' times the value, OPT, of an optimum solution.

	:<math>\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}</math>		:<math>\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}</math>

OAbot: Open access bot: doi added to citation with #oabot.

2023-08-13T11:07:37Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 11:07, 13 August 2023
Line 30:		Line 30:
	Approximation algorithms as a research area is closely related to and informed by [[Hardness of approximation\|inapproximability theory]] where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of [[Reduction (complexity)\|reductions]]. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.008196 unless P = NP, Karpinski, Lampis, Schmied.<ref>{{Cite journal\|last1=Karpinski\|first1=Marek\|last2=Lampis\|first2=Michael\|last3=Schmied\|first3=Richard\|date=2015-12-01\|title=New inapproximability bounds for TSP\|journal=Journal of Computer and System Sciences\|volume=81\|issue=8\|pages=1665–1677\|doi=10.1016/j.jcss.2015.06.003\|arxiv=1303.6437}}</ref> Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5.		Approximation algorithms as a research area is closely related to and informed by [[Hardness of approximation\|inapproximability theory]] where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of [[Reduction (complexity)\|reductions]]. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.008196 unless P = NP, Karpinski, Lampis, Schmied.<ref>{{Cite journal\|last1=Karpinski\|first1=Marek\|last2=Lampis\|first2=Michael\|last3=Schmied\|first3=Richard\|date=2015-12-01\|title=New inapproximability bounds for TSP\|journal=Journal of Computer and System Sciences\|volume=81\|issue=8\|pages=1665–1677\|doi=10.1016/j.jcss.2015.06.003\|arxiv=1303.6437}}</ref> Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5.

	While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)\|Independent Set]]<ref>{{Cite journal\|last1=Feige\|first1=Uriel\|last2=Goldwasser\|first2=Shafi\|last3=Lovász\|first3=Laszlo\|last4=Safra\|first4=Shmuel\|last5=Szegedy\|first5=Mario\|date=March 1996\|title=Interactive Proofs and the Hardness of Approximating Cliques\|journal=J. ACM\|volume=43\|issue=2\|pages=268–292\|doi=10.1145/226643.226652\|issn=0004-5411\|doi-access=free}}</ref> and the famous [[PCP theorem]],<ref>{{Cite journal\|last1=Arora\|first1=Sanjeev\|last2=Safra\|first2=Shmuel\|date=January 1998\|title=Probabilistic Checking of Proofs: A New Characterization of NP\|journal=J. ACM\|volume=45\|issue=1\|pages=70–122\|doi=10.1145/273865.273901\|s2cid=751563\|issn=0004-5411}}</ref> that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that [[David S. Johnson\|Johnson's]] 1974 approximation algorithms for [[Maximum satisfiability problem\|Max SAT]], [[Set cover problem\|set cover]], [[Independent set (graph theory)\|independent set]] and [[Graph coloring\|coloring]] all achieve the optimal approximation ratio, assuming P ≠ NP.<ref>{{Cite journal\|last=Johnson\|first=David S.\|date=1974-12-01\|title=Approximation algorithms for combinatorial problems\|journal=Journal of Computer and System Sciences\|volume=9\|issue=3\|pages=256–278\|doi=10.1016/S0022-0000(74)80044-9\|doi-access=free}}</ref>		While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)\|Independent Set]]<ref>{{Cite journal\|last1=Feige\|first1=Uriel\|last2=Goldwasser\|first2=Shafi\|last3=Lovász\|first3=Laszlo\|last4=Safra\|first4=Shmuel\|last5=Szegedy\|first5=Mario\|date=March 1996\|title=Interactive Proofs and the Hardness of Approximating Cliques\|journal=J. ACM\|volume=43\|issue=2\|pages=268–292\|doi=10.1145/226643.226652\|issn=0004-5411\|doi-access=free}}</ref> and the famous [[PCP theorem]],<ref>{{Cite journal\|last1=Arora\|first1=Sanjeev\|last2=Safra\|first2=Shmuel\|date=January 1998\|title=Probabilistic Checking of Proofs: A New Characterization of NP\|journal=J. ACM\|volume=45\|issue=1\|pages=70–122\|doi=10.1145/273865.273901\|s2cid=751563\|issn=0004-5411\|doi-access=free}}</ref> that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that [[David S. Johnson\|Johnson's]] 1974 approximation algorithms for [[Maximum satisfiability problem\|Max SAT]], [[Set cover problem\|set cover]], [[Independent set (graph theory)\|independent set]] and [[Graph coloring\|coloring]] all achieve the optimal approximation ratio, assuming P ≠ NP.<ref>{{Cite journal\|last=Johnson\|first=David S.\|date=1974-12-01\|title=Approximation algorithms for combinatorial problems\|journal=Journal of Computer and System Sciences\|volume=9\|issue=3\|pages=256–278\|doi=10.1016/S0022-0000(74)80044-9\|doi-access=free}}</ref>

	== Practicality ==		== Practicality ==

Citation bot: Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 134/2306

2023-08-06T05:58:53Z

Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 134/2306

← Previous revision		Revision as of 05:58, 6 August 2023
Line 4:		Line 4:
	The design and [[mathematical analysis\|analysis]] of approximation algorithms crucially involves a [[mathematical proof]] certifying the quality of the returned solutions in the worst case.<ref name="Bernard. 2011"/> This distinguishes them from [[heuristic (computer science)\|heuristics]] such as [[Simulated annealing\|annealing]] or [[genetic algorithm]]s, which find reasonably good solutions on some inputs, but provide no clear indication at the outset on when they may succeed or fail.		The design and [[mathematical analysis\|analysis]] of approximation algorithms crucially involves a [[mathematical proof]] certifying the quality of the returned solutions in the worst case.<ref name="Bernard. 2011"/> This distinguishes them from [[heuristic (computer science)\|heuristics]] such as [[Simulated annealing\|annealing]] or [[genetic algorithm]]s, which find reasonably good solutions on some inputs, but provide no clear indication at the outset on when they may succeed or fail.

	There is widespread interest in [[theoretical computer science]] to better understand the limits to which we can approximate certain famous optimization problems. For example, one of the long-standing open questions in computer science is to determine whether there is an algorithm that outperforms the 2-approximation for the Steiner Forest problem by Agrawal et al.<ref>{{Cite ~~journal~~ \|last1=Agrawal \|first1=Ajit \|last2=Klein \|first2=Philip \|last3=Ravi \|first3=R. ~~\|date=1991~~ \|title=~~When~~ ~~trees~~ ~~collide:~~ an ~~approximation~~ ~~algorithm~~ ~~for~~ ~~the~~ ~~generalized~~ ~~Steiner~~ ~~problem~~ on ~~networks~~ \|url=http://portal.acm.org/citation.cfm?doid=103418.103437 ~~\|journal=Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing - STOC '91~~ \|language=en \|location=New Orleans, Louisiana, United States \|publisher=ACM Press \|pages=134–144 \|doi=10.1145/103418.103437 \|isbn=978-0-89791-397-3\|s2cid=1245448 }}</ref> The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the [[Semidefinite programming#Example 3 (Goemans–Williamson max cut approximation algorithm)\|Goemans–Williamson algorithm]] for [[maximum cut]], which solves a graph theoretic problem using high dimensional geometry.<ref>{{Cite journal\|last1=Goemans\|first1=Michel X.\|last2=Williamson\|first2=David P.\|date=November 1995\|title=Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming\|journal=J. ACM\|volume=42\|issue=6\|pages=1115–1145\|doi=10.1145/227683.227684\|issn=0004-5411\|citeseerx=10.1.1.34.8500\|s2cid=15794408}}</ref>		There is widespread interest in [[theoretical computer science]] to better understand the limits to which we can approximate certain famous optimization problems. For example, one of the long-standing open questions in computer science is to determine whether there is an algorithm that outperforms the 2-approximation for the Steiner Forest problem by Agrawal et al.<ref>{{Cite book \|last1=Agrawal \|first1=Ajit \|last2=Klein \|first2=Philip \|last3=Ravi \|first3=R. \|title=Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 \|chapter=When trees collide \|date=1991 \|chapter-url=http://portal.acm.org/citation.cfm?doid=103418.103437 \|language=en \|location=New Orleans, Louisiana, United States \|publisher=ACM Press \|pages=134–144 \|doi=10.1145/103418.103437 \|isbn=978-0-89791-397-3\|s2cid=1245448 }}</ref> The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the [[Semidefinite programming#Example 3 (Goemans–Williamson max cut approximation algorithm)\|Goemans–Williamson algorithm]] for [[maximum cut]], which solves a graph theoretic problem using high dimensional geometry.<ref>{{Cite journal\|last1=Goemans\|first1=Michel X.\|last2=Williamson\|first2=David P.\|date=November 1995\|title=Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming\|journal=J. ACM\|volume=42\|issue=6\|pages=1115–1145\|doi=10.1145/227683.227684\|issn=0004-5411\|citeseerx=10.1.1.34.8500\|s2cid=15794408}}</ref>

	== Introduction ==		== Introduction ==