@inproceedings{d636c93b11804d65bbfe61644c2cb150,
title = "The orienteering problem in the plane revisited",
abstract = "We consider the orienteering problem: Given a set P of n points in the plane, a starting point r ε P, and a length constraint B, one needs to and a tour starting at r that visits as many points of P as possible and of length not exceeding B. We present a (1 -ε)-approximation algorithm for this problem that runs in no(I/ε) time, and visits at least (1 - ε)k opt points of P, where kopt is the number of points visited by the optimal solution. This is the first polynomial time approximation scheme (PTAS) for this problem. The algorithm also works in higher dimensions.",
keywords = "Approximation, Orienteering problem, k-TSP",
author = "Ke Chen and Sariel Har-Peled",
year = "2006",
doi = "10.1145/1137856.1137893",
language = "English (US)",
isbn = "1595933409",
series = "Proceedings of the Annual Symposium on Computational Geometry",
publisher = "Association for Computing Machinery",
pages = "247--253",
booktitle = "Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06",
address = "United States",
note = "22nd Annual Symposium on Computational Geometry 2006, SCG'06 ; Conference date: 05-06-2006 Through 07-06-2006",
}