Approximation algorithms for geometric optimization problems
We survey recent developments in the study of approximation algorithms for NP-hard geometric optimization problems. We focus on those problems which, given a set of points. ask For a graph of a specified type on those points with the minimum total edge length, such as the traveling salesman problem, the Steiner minimum tree problem, and the k-minimum spanning tree problem. In a recent few years, several polynomial time approximation schemes are discovered for these problems. All of them are dynamic programming algorithms based on some geometric theorems that assert the existence of a good approximate solution with a simple recursive decomposition structure. Our emphasis is on these geometric theorems, which have potential uses in the design and analysis of heuristic algorithms.
approximation algorithm geometric optimization traveling salesman np-hard optimization problems ptas steiner tree