알고리즘서지만 확인
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsSanjeev Arora · 1998Journal of the ACM 45(5), 753–782쪽 (1998) · 학회 발표 FOCS 1996 (37th Annual Symposium on Foundations of Computer Science), 2–11쪽 — 학회판 제목은 「Polynomial time approximation schemes for Euclidean TSP and other geometric problems」평면 위 점들의 외판원 문제에서 임의의 c > 1 에 대해 최적의 (1 + 1/c) 배 이내인 경로를 다항 시간에 찾는 근사 방식을 내놓은 논문이다. 초록에 따르면 그전의 최선은 Christofides 의 3/2 근사였다. NP-난해 문제라도 입력에 기하 구조가 있으면 원하는 만큼 가까이 근사할 수 있다는 예로, 근사 불가능성 결과와 짝지어 설명하는 글에 쓴다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 확인하고 학술지판 기록의 초록을 읽었다.