The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
우리는 NP-하드 기하학적 최적화 문제에 대한 근사 알고리즘 연구의 최근 개발 상황을 조사합니다. 우리는 점 집합이 주어졌을 때 이동하는 판매원 문제, Steiner 최소 트리 문제, k- 최소 스패닝 트리 문제. 최근 몇 년 동안 이러한 문제에 대한 여러 다항식 시간 근사 방식이 발견되었습니다. 이들 모두는 간단한 재귀 분해 구조를 통해 좋은 근사해의 존재를 주장하는 일부 기하학적 정리를 기반으로 하는 동적 프로그래밍 알고리즘입니다. 우리는 경험적 알고리즘의 설계 및 분석에 잠재적으로 사용될 수 있는 이러한 기하학적 정리에 중점을 둡니다.
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.
부
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
부
@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},}
부
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 -