Abstract.
Traveling Salesman, Steiner Tree, and many other famous geometric optimization problems are NP-hard. Since we do not expect to design efficient algorithms that solve these problems optimally, researchers have tried to design approximation algorithms, which can compute a provably near-optimal solution in polynomial time.
We survey such algorithms, in particular a new technique developed over the past few years that allows us to design approximation schemes for many of these problems. For any fixed constant c> 0, the algorithm can compute a solution whose cost is at most (1 + c) times the optimum. (The running time is polynomial for every fixed c> 0, and in many cases is even nearly linear.) We describe how these schemes are designed, and survey the status of a large number of problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: December 2, 2002 / Accepted: April 28, 2003 Published online: May 28, 2003
Supported by a David and Lucile Packard Fellowship, NSF grant CCR-0098180, NSF ITR grant CCR-0205594
Rights and permissions
About this article
Cite this article
Arora, S. Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program., Ser. B 97, 43–69 (2003). https://doi.org/10.1007/s10107-003-0438-y
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0438-y