Approximation schemes for NP-hard geometric optimization problems: a survey

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.