Talk:Approximation algorithm - Revision history

Cewbot: Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{Maths rating}}, {{WPCS}}. Remove 1 deprecated parameter: field.

2024-01-14T23:12:20Z

Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{Maths rating}}, {{WPCS}}. Remove 1 deprecated parameter: field.

← Previous revision		Revision as of 23:12, 14 January 2024
Line 1:		Line 1:
			{{WikiProject banner shell\|class=Start\|1=
	{{maths rating\|priority=mid\|class=start\|field=discrete}}
			{{WikiProject Mathematics\|priority=mid}}
	{{WPCS\|importance=high\|class=start}}
			{{WikiProject Computer science\|importance=high}}
			}}

	==Rough draft of research to cite and incorporate, thanks==		==Rough draft of research to cite and incorporate, thanks==

PrimeBOT: Replace magic links with templates per local RfC - BRFA

2017-06-21T15:15:21Z

Replace magic links with templates per local RfC - BRFA

← Previous revision		Revision as of 15:15, 21 June 2017
Line 35:		Line 35:
	^ a b c d e Viggo Kann (1992). On the Approximability of NP-complete Optimization Problems.		^ a b c d e Viggo Kann (1992). On the Approximability of NP-complete Optimization Problems.
	^ Johan Håstad (1999). "Some Optimal Inapproximability Results". Journal of the ACM.		^ Johan Håstad (1999). "Some Optimal Inapproximability Results". Journal of the ACM.
	Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3540653678.		Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. {{ISBN\|3540653678}}.
	Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 35: Approximation Algorithms, pp. 1022–1056.		Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN\|0-262-03293-7}}. Chapter 35: Approximation Algorithms, pp. 1022–1056.
	Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More		Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. {{ISBN\|0-534-94968-1}}. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More
	External links		External links
	Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.		Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.

173.164.197.30: Rought draft~~~~

2011-03-25T05:06:03Z

Rought draft~~~~

← Previous revision		Revision as of 05:06, 25 March 2011
Line 2:		Line 2:
	{{WPCS\|importance=high\|class=start}}		{{WPCS\|importance=high\|class=start}}

			==Rough draft of research to cite and incorporate, thanks==

			In computer science and operations research, we use approximation algorithms to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since efficient polynomial time exact algorithms solving NP-hard problems, one settles for polynomial time sub-optimal solutions. Unlike heuristics, where usually we only find reasonably good solutions reasonably fast, one wants provable solution quality and provable run time bounds. Ideally, the approximation is optimal up to a small constant factor (for instance within 5% optimal solution). Approximation algorithms are used often for problems where exact polynomial-time algorithms are known but are too expensive due to the input size.
			A typical example for an approximation algorithm is the vertex cover in graphs: find an uncovered edge and add both endpoints to the vertex cover, until zero endpoints remain. It is clear that the resulting cover is at most twice as large as the optimal one. This is a constant factor approximation algorithm of factor two.
			NP-hard problems vary greatly in their approximability; some, such as the bin packing problem, can be approximated within any factor greater than 1 (a family of approximation algorithms often called a polynomial time approximation scheme or PTAS). Others are possible to approximate but without a constant, or even polynomial factor unless P = NP, such as the maximum clique problem.
			NP-hard problems we can express as integer programs (IP) solved exactly in exponential time. Many approximation algorithms emerge from the linear programming relaxation of the integer program.
			Some approximation algorithms are suitable for some practical applications. They often use IP/LP/Semidefinite solvers, complex data structures or sophisticated algorithmic techniques leading to difficult implementation problems. Also, some approximation algorithms have impractical running times though they do run in polynomial time, for example O(n2000). Yet the study of expensive algorithms is a completely practical pursuit as it yields valuable insights. A classic example is the initial PTAS for Euclidean TSP due to Sanjeev Arora had prohibitive running time, yet ithin a year, Arora refined the ideas into a linear time algorithm. These types of algorithms are worthwhile in applications where we can justify the running time and cost e.g. computational biology, financial engineering, transportation planning, and inventory management. In these scenarios almorithms compete with direct IP corresponding formulations.
			A limit to the approach refers to optimization problems "pure" decision problems like satisfiability, though it is possible to conceive optimization versions of these problems including the maximum satisfiability problem or (Max SAT).
			Inapproximability has been a fruitful area of research in computational complexity theory since the 1990 result of Feige, Goldwasser, Lovasz, Safra and Szegedy on the inapproximability of Independent Set. Now the time has come to embrace the potential gains of approxmability provided these new theories we discuss. Looking back, after Arora et al. proved the PCP theorem in 1991, it was later shown Johnson's 1974 approximation algorithms for Max SAT, Set Cover, Independent Set and Coloring all achieve optimal approximation ratio, assuming P != NP.
			Consider these two items: Performance guarantee and Epsiolon term.
			Performance guarantees for some approximation algorithms allow us to prove certain properties about the approximation of the optimum result. For example, in case ρ-approximation algorithm A has proof value/cost, f(x) approximate solution A(x) instance x will be less (more or less, depending on) factor ρ times value OPT optimum solution.
			\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}
			Factor ρ relative performance guarantee approximation algorithm absolute performance guarantee bounds error c proven for instant x
			(\mathrm{OPT} - c) \leq f(x) \leq (\mathrm{OPT} + c).
			Similarly, performance guarantee, R(x,y) solution y to instance x defines
			R(x,y) = \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right )
			where f(y) is value/cost solution y for instant x. Performance guarantee is greater than or equal to 1 and equal to 1 optimal solution. If algorithm A guarantees solutions performance guarantee return at most r(n) A is an r(n)-approximation algorithm approximation ratio r(n). Problem r(n)-approximation algorithm is r(n)-approximable approximation ratio r(n).[1][2]
			Minimization problems guarantees two different factors provide the same result maximization problem relative performance guarantee ρ is equivalent to performance guarantee r = ρ − 1. In literature both definitions are common and define clear maximization problem ρ ≤ 1 while r ≥ 1.
			Absolute performance guarantee ΡA approximation algorithm A x refers to instant problem RA(x) is performance guarantee A on x (i.e. ρ for problem instant x) =:
			\Rho_A = \inf \{ r \geq 1 \,\|\, R_A(I) \leq r, \forall x \}
			ΡA=largest bound approximation ratio r sees over possible instant problem asymptotic performance ratio R_A^\infty=:
			R_A^\infty = \inf \{ r \geq 1 \,\|\, \exists n \in \mathbb{Z}^+, R_A(I) \leq r, \forall x, \|x\| \geq n\}
			Same absolute performance ratio lower bound n problem size problem instant two type ratio result exist algorithm between two significant.
			Performance guarantee r-approx[1][2] ρ-approx rel. error[2] rel. error[1] norm. rel. error[1][2] abs. error[1][2]
			max: f(x) \geq r − 1OPT ρOPT (1 − c)OPT (1 − c)OPT (1 − c)OPT -cBEST OPT − c
			min: f(x) \leq rOPT ρOPT (1 + c)OPT (1 − c) − 1OPT (1 − c) − 1OPT - cBEST OPT + c
			Epsilon term IN literature approximation ratio maximization (minimization) problem c - ϵ (min: c + ϵ) means algorithm approximation ratio cϵ for arbitrary ϵ > 0 ratio show ϵ = 1 example of optimal approximability — existence of approximation — ratio 7 / 8 + ϵ for satisfiable MAX-3SAT instant due Johan Håstad.[3] Mention previously c = 1 problem polynomial-time approximation scheme.
			ϵ-term appearance approximation algorithm introduces multiplicative error plus constant error minimum optimum instant size n infinity as n infinity approximation ratio c k / OPT = c o(1) some constant c + k arbitrary ϵ > 0 link N term k / OPT < ϵ every n ≥ N every fixed ϵ, instant size n < N brute force solution shows approximation ratio exists approximation algorithm guarantee — c ϵ to every ϵ > 0.
			See also domain analysis guarantee rank term solution computes.
			References
			^ a b c d e G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.
			^ a b c d e Viggo Kann (1992). On the Approximability of NP-complete Optimization Problems.
			^ Johan Håstad (1999). "Some Optimal Inapproximability Results". Journal of the ACM.
			Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3540653678.
			Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 35: Approximation Algorithms, pp. 1022–1056.
			Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More
			External links
			Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.
			Categories: Computational complexity theory \| Approximation algorithms
			[[Special:Contributions/173.164.197.30\|173.164.197.30]] ([[User talk:173.164.197.30\|talk]]) 05:06, 25 March 2011 (UTC)

	There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [http://www.springerlink.com/content/etkt6c2tl8a58tju/] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 16:50, 22 August 2006 (UTC)		There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [http://www.springerlink.com/content/etkt6c2tl8a58tju/] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 16:50, 22 August 2006 (UTC)

RobinK: added rating

2009-12-07T04:10:12Z

added rating

← Previous revision		Revision as of 04:10, 7 December 2009
Line 1:		Line 1:
			{{maths rating\|priority=mid\|class=start\|field=discrete}}
			{{WPCS\|importance=high\|class=start}}


	There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [http://www.springerlink.com/content/etkt6c2tl8a58tju/] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 16:50, 22 August 2006 (UTC)		There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [http://www.springerlink.com/content/etkt6c2tl8a58tju/] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 16:50, 22 August 2006 (UTC)

SineBot: Signing comment by C. lorenz - "References for Approximation Guarantees"

2009-04-24T18:24:29Z

Signing comment by C. lorenz - "References for Approximation Guarantees"

← Previous revision		Revision as of 18:24, 24 April 2009
Line 6:		Line 6:

	== References for Approximation Guarantees ==		== References for Approximation Guarantees ==
	Seeing how there are many different and varying definitions used for approximation guarantees, I would preferably like to see inline sources. The article currently uses ρ-approximation algorithms (relative performance guarantee) and I strongly believe that the definition is taken from Handbook of Approximation Algorithms and Metaheuristics but I cannot verify this myself. The definition used also agrees with "factor δ approximation algorithms" from Vazirani's book but it does not agree with the usual performance ratio which in Cormen et.al. uses the symbol ρ.		Seeing how there are many different and varying definitions used for approximation guarantees, I would preferably like to see inline sources. The article currently uses ρ-approximation algorithms (relative performance guarantee) and I strongly believe that the definition is taken from Handbook of Approximation Algorithms and Metaheuristics but I cannot verify this myself. The definition used also agrees with "factor δ approximation algorithms" from Vazirani's book but it does not agree with the usual performance ratio which in Cormen et.al. uses the symbol ρ. <small><span class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:C. lorenz\|C. lorenz]] ([[User talk:C. lorenz\|talk]] • [[Special:Contributions/C. lorenz\|contribs]]) 18:23, 24 April 2009 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

C. lorenz: References for Approximation Guarantees

2009-04-24T18:23:16Z

References for Approximation Guarantees

← Previous revision		Revision as of 18:23, 24 April 2009
Line 4:		Line 4:

	One is a function, the other is a set. You are right though, it'd probably be less confusing to use another variable.--[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 09:26, 20 June 2007 (UTC)		One is a function, the other is a set. You are right though, it'd probably be less confusing to use another variable.--[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 09:26, 20 June 2007 (UTC)

			== References for Approximation Guarantees ==
			Seeing how there are many different and varying definitions used for approximation guarantees, I would preferably like to see inline sources. The article currently uses ρ-approximation algorithms (relative performance guarantee) and I strongly believe that the definition is taken from Handbook of Approximation Algorithms and Metaheuristics but I cannot verify this myself. The definition used also agrees with "factor δ approximation algorithms" from Vazirani's book but it does not agree with the usual performance ratio which in Cormen et.al. uses the symbol ρ.

Zzuuzz: moved Talk:Nathan Byrne to Talk:Approximation algorithm over redirect: rvv

2007-11-06T15:56:43Z

moved Talk:Nathan Byrne to Talk:Approximation algorithm over redirect: rvv

← Previous revision	Revision as of 15:56, 6 November 2007
(No difference)

Whodoesthis: moved Talk:Approximation algorithm to Talk:Nathan Byrne

2007-11-06T11:44:42Z

moved Talk:Approximation algorithm to Talk:Nathan Byrne

← Previous revision	Revision as of 11:44, 6 November 2007
(No difference)

David Eppstein: rm inappropriate bot tag per discussion at Wikipedia_talk:WikiProject_Logic

2007-08-01T01:32:36Z

rm inappropriate bot tag per discussion at Wikipedia_talk:WikiProject_Logic

← Previous revision		Revision as of 01:32, 1 August 2007
Line 1:		Line 1:

	{{Logic2}}

	There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [http://www.springerlink.com/content/etkt6c2tl8a58tju/] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 16:50, 22 August 2006 (UTC)		There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [http://www.springerlink.com/content/etkt6c2tl8a58tju/] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 16:50, 22 August 2006 (UTC)

SatyrBot: SatyrBot auto-adding tag to talk page. See User:SatyrBot/Current project

2007-07-31T06:22:06Z

SatyrBot auto-adding tag to talk page. See User:SatyrBot/Current project

← Previous revision		Revision as of 06:22, 31 July 2007
Line 1:		Line 1:

			{{Logic2}}

	There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [http://www.springerlink.com/content/etkt6c2tl8a58tju/] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 16:50, 22 August 2006 (UTC)		There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [http://www.springerlink.com/content/etkt6c2tl8a58tju/] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --[[User:NotQuiteEXPComplete\|NotQuiteEXPComplete]] 16:50, 22 August 2006 (UTC)