| LC control no. | sh2009010988 |
|---|---|
| Topical heading | Approximation algorithms |
| See also | Heuristic algorithms |
| Found in | Work cat.: Williamson, D. Lecture notes on approximation algorithms, 1998. Dictionary of algorithms and data structures, via WWW, Dec. 18, 2009 (approximation algorithm -- An algorithm to solve an optimization problem that runs in polynomial time in the length of the input and outputs a solution that is guaranteed to be close to the optimal solution) Könemann, J. Approximation algorithms for minimum cost low degree subgraphs, 2003: p. 2 (Approximation algorithms are heuristic algorithms supplied with an upper bound on the worst case ratio between the value of any approximation solution and that of an optimum solution) Tan, K. On the role of partition inequalities in classical algorithms for Steiner problems in graphs, 2007: p. 2 (we resort to finding polynomial-time algorithms that efficiently solve the problems approximately, i.e., approximation algorithms; an approximation algorithm is a heuristic algorithm, which does not solve the given optimization problem exactly, but guarantees an upper bound on the worst case ratio between the value of any approximation solution and that of an optimum solution) FOLDOC, Dec. 18, 2009 (approximation algorithm -- An algorithm for an optimisation problem that generates feasible but not necessarily optimal solutions; unlike "heuristic," the term "approximation algorithm" often implies some proven worst or average case bound on performance) Wikipedia WWW site, Jan. 4, 2010 (Approximation algorithms; in computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems) |
 |  |  |