검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

Approximation Algorithms for Geometric Optimization Problems 기하학적 최적화 문제에 대한 근사 알고리즘

Hisao TAMAKI

  • 조회수

    0

  • 이것을 인용

요약 :

우리는 NP-하드 기하학적 최적화 문제에 대한 근사 알고리즘 연구의 최근 개발 상황을 조사합니다. 우리는 점 집합이 주어졌을 때 이동하는 판매원 문제, Steiner 최소 트리 문제, k- 최소 스패닝 트리 문제. 최근 몇 년 동안 이러한 문제에 대한 여러 다항식 시간 근사 방식이 발견되었습니다. 이들 모두는 간단한 재귀 분해 구조를 통해 좋은 근사해의 존재를 주장하는 일부 기하학적 정리를 기반으로 하는 동적 프로그래밍 알고리즘입니다. 우리는 경험적 알고리즘의 설계 및 분석에 잠재적으로 사용될 수 있는 이러한 기하학적 정리에 중점을 둡니다.

발행
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.455-461
발행일
2000/03/25
공개일
온라인 ISSN
DOI
원고의 종류
INVITED SURVEY PAPER
범주
기하학적 문제에 대한 알고리즘

작성자

키워드