Editing Approximation algorithm (section)

== Practicality ==
{{seealso|Galactic algorithm}}
Not all approximation algorithms are suitable for direct practical applications. Some involve solving non-trivial [[Linear programming relaxation|linear programming]]/[[Semidefinite programming|semidefinite]] relaxations (which may themselves invoke the [[Ellipsoid method|ellipsoid algorithm]]), complex data structures, or sophisticated algorithmic techniques, leading to difficult implementation issues or improved running time performance (over exact algorithms) only on impractically large inputs. Implementation and running time issues aside, the guarantees provided by approximation algorithms may themselves not be strong enough to justify their consideration in practice. Despite their inability to be used "out of the box" in practical applications, the ideas and insights behind the design of such algorithms can often be incorporated in other ways in practical algorithms. In this way, the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights.

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>