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 find 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 n^O(1/ε) time, and visits at least (1−ε)k_opt points of P, where k_opt 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.

REFERENCES

• 1: Esther M. Arkin , Joseph S. B. Mitchell , Giri Narasimhan, Resource-constrained geometric network optimization, Proceedings of the fourteenth annual symposium on Computational geometry, p.307-316, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276919]
• 2: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 3: S. Arora. Approximation schemes for np-hard geometric optimization problems: a survey. Mathematical Programming, 97:43--69, 2003.
• 4: Sanjeev Arora , George Karakostas, Approximation Schemes for Minimum Latency Problems, SIAM Journal on Computing, v.32 n.5, p.1317-1337, 2003 [doi>10.1137/S0097539701399654]
• 5: Nikhil Bansal , Avrim Blum , Shuchi Chawla , Adam Meyerson, Approximation algorithms for deadline-TSP and vehicle routing with time-windows, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007385]
• 6: Reuven Bar-Yehuda , Guy Even , Shimon Shahar, On approximating a geometric prize-collecting traveling salesman problem with time windows, Journal of Algorithms, v.55 n.1, p.76-92, April 2005 [doi>10.1016/j.jalgor.2003.11.002]
• 7: Avrim Blum , Shuchi Chawla , David R. Karger , Terran Lane , Adam Meyerson , Maria Minkoff, Approximation Algorithms for Orienteering and Discounted-Reward TSP, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.46, October 11-14, 2003
• 8: Chandra Chekuri , Martin Pal, A Recursive Greedy Algorithm for Walks in Directed Graphs, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.245-253, October 23-25, 2005 [doi>10.1109/SFCS.2005.9]
• 9: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 10: J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 15, pages 633--701. Elsevier, 2000.
• 11: Paolo Toth , Daniele Vigo, The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 01

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
k-TSP, approximation, orienteering problem