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

Traveling Salesman, Steiner Tree, and many other famous genetic 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.