The search functionality is under construction.
The search functionality is under construction.

Approximation Algorithms for Geometric Optimization Problems

Hisao TAMAKI

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.455-461
Publication Date
2000/03/25
Publicized
Online ISSN
DOI
Type of Manuscript
INVITED SURVEY PAPER
Category
Algorithms for Geometric Problems

Authors

Keyword