Home Bookmarks Papers Blog

The Orienteering Problem in the Plane Revisited

Ke Chen and Sariel Har-Peled.

We consider the orienteering problem : Given a set P of n points in the plane, a starting point r in P, and a length constraint B, one need 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 nO(1/µ) time, and visits at least (1-µ)k points of P, where k is the number of points visited by the optimal solution. This is the first polynomial time approximation scheme(PTAS) for this problem.

Postscript, PDF.

@string{SICOMP = "SIAM J. Comput."}

  author       = {K. Chen and S. {Har-Peled}},
  title        = {The {Euclidean} Orienteering Problem Revisited},
  journal      = SICOMP,
  volume       = {38},
  number       = {1},
  year         = {2008},
  pages        = {385--397}

Last modified: Sun Dec 7 13:50:40 CST 2008