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

摘要: 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 optimally, researchers have tried approximation algorithms, which can compute a provably near-optimal solution in polynomial time. We survey such particular new technique developed over the past few years allows us schemes for of problems. For any fixed constant c> 0, algorithm whose cost is at most (1 + c) times optimum. (The running time every cases even nearly linear.) describe how designed, status large number