Approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as
- Comment
- enIn computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as
- Has abstract
- enIn computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines. The design and analysis of approximation algorithms crucially involves a mathematical proof certifying the quality of the returned solutions in the worst case. This distinguishes them from heuristics such as annealing or genetic algorithms, 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 1.5 approximation algorithm of Christofides to the metric traveling salesman problem. 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 Goemans–Williamson algorithm for maximum cut, which solves a graph theoretic problem using high dimensional geometry.
- Hypernym
- Algorithms
- Is primary topic of
- Approximation algorithm
- Label
- enApproximation algorithm
- Link from a Wikipage to an external page
- www.csc.kth.se/tcs/compendium/
- Link from a Wikipage to another Wikipage
- Algorithm
- Approximation
- Approximation Algorithms for NP-Hard problems
- Approximation-preserving reduction
- APX
- Cambridge University Press
- Category:Approximation algorithms
- Category:Computational complexity theory
- Charles E. Leiserson
- Christofides algorithm
- Clifford Stein
- Clique problem
- Computer science
- Constant factor approximation algorithm
- Convex programming
- David S. Johnson
- David Shmoys
- Domination analysis
- Dorit S. Hochbaum
- Dynamic programming
- Ellipsoid method
- Euclidean traveling salesman problem
- Éva Tardos
- Exact algorithm
- Genetic algorithm
- Gerhard J. Woeginger
- Graph coloring
- Greedy algorithm
- Hardness of approximation
- Heuristic (computer science)
- Independent set (graph theory)
- Introduction to Algorithms
- Jan Karel Lenstra
- Johan Håstad
- Joseph S. B. Mitchell
- Knapsack problem
- Linear programming
- Linear programming relaxation
- Local search (optimization)
- Marek Karpinski
- Matching (graph theory)
- MAX-3SAT
- Maximum cut
- Maximum satisfiability problem
- NP-completeness
- NP-hardness
- Operations research
- Optimization problem
- P = NP
- PCP theorem
- Polynomial time approximation scheme
- Polynomial-time approximation scheme
- P versus NP problem
- Reduction (complexity)
- Ronald L. Rivest
- Sanjeev Arora
- Scheduling (computing)
- Semidefinite programming
- Set cover problem
- Simulated annealing
- Theoretical computer science
- Thomas H. Cormen
- Threshold of approximability
- Time complexity
- Travelling salesman problem
- Unique games conjecture
- Vertex cover
- SameAs
- 4500954-5
- 4ohTC
- Algorithme d'approximation
- Algoritmo de aproximação
- Algoritmo de aproximación
- Algoritmo di approssimazione
- Algorytm aproksymacyjny
- Approximation algorithm
- Approximationsalgorithmus
- Aproximační algoritmy
- m.02qc78
- Q621751
- Thuật toán xấp xỉ
- Аппроксимационный алгоритм
- Апроксимациони алгоритам
- Апроксимаційний алгоритм
- אלגוריתם קירוב
- الگوریتم تقریبی
- ขั้นตอนวิธีการประมาณ
- 近似アルゴリズム
- 近似算法
- 근사 알고리즘
- SeeAlso
- Galactic algorithm
- Subject
- Category:Approximation algorithms
- Category:Computational complexity theory
- WasDerivedFrom
- Approximation algorithm?oldid=1118311023&ns=0
- WikiPageLength
- 20966
- Wikipage page ID
- 563105
- Wikipage revision ID
- 1118311023
- WikiPageUsesTemplate
- Template:Authority control
- Template:Citation
- Template:Cite book
- Template:ISBN
- Template:More footnotes
- Template:Optimization algorithms
- Template:Reflist
- Template:Seealso
- Template:Short description