The search functionality is under construction.

The search functionality is under construction.

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hisao TAMAKI, "Approximation Algorithms for Geometric Optimization Problems" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 455-461, March 2000, doi: .

Abstract: 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.

URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_455/_p

Copy

@ARTICLE{e83-d_3_455,

author={Hisao TAMAKI, },

journal={IEICE TRANSACTIONS on Information},

title={Approximation Algorithms for Geometric Optimization Problems},

year={2000},

volume={E83-D},

number={3},

pages={455-461},

abstract={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.},

keywords={},

doi={},

ISSN={},

month={March},}

Copy

TY - JOUR

TI - Approximation Algorithms for Geometric Optimization Problems

T2 - IEICE TRANSACTIONS on Information

SP - 455

EP - 461

AU - Hisao TAMAKI

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E83-D

IS - 3

JA - IEICE TRANSACTIONS on Information

Y1 - March 2000

AB - 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.

ER -