skip to main content
10.5555/1347082.1347155acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

Improved algorithms for orienteering and related problems

Published: 20 January 2008 Publication History

Abstract

In this paper we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering-problem is the following: Given an edge-weighted graph G = (V, E) (directed or undirected), two nodes s, tV and a budget B, find an s-t walk in G of total length at most B that maximizes the number of distinct nodes visited by the walk. This problem is closely related to tour problems such as TSP as well as network design problems such as k-MST. Our main results are the following.
• A 2 + ε approximation in undirected graphs, improving upon the 3-approximation from [6].
• An O(log2 OPT) approximation in directed graphs. Previously, only a quasi-polynomial time algorithm achieved a poly-logarithmic approximation [14] (a ratio of O (log OPT)).
The above results are based on, or lead to, improved algorithms for several other related problems.

References

[1]
R. Ahuja, T. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River, NJ, 1993
[2]
E. Arkin, J. Mitchell, and G. Narasimhan. Resource-constrained geometric network optimization. Proc. of ACM SoCG, 307--316, 1998.
[3]
S. Arora and G. Karakostas. A 2 + ε approximation algorithm for the k-mst problem. Proc. of ACM-SIAM SODA, 754--759, 2000.
[4]
B. Awerbuch, Y. Azar, A. Blum and S. Vempala. New Approximation Guarantees for Minimum Weight k-Trees and Prize-Collecting Salesmen. SIAM J. on Computing, 28(1):254--262, 1999. Preliminary version in Proc. of ACM STOC, 1995.
[5]
E. Balas. The prize collecting traveling salesman problem. Networks, 19:621--636, 1989.
[6]
N. Bansal, A. Blum, S. Chawla, and A. Meyerson. Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows. Proc. of ACM STOC, 166--174, 2004.
[7]
R. Bar-Yehuda, G. Even and S. Shahar. On Approximating a Geometric Prize-Collecting Traveling Salesman Problem with Time Windows. J. of Algorithms, 55(1):76--92, 2005.
[8]
M. Bläser. A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality. Proc. of ACM-SIAM SODA, 638--645, 2002.
[9]
A. Blum, S. Chawla, D. Karger, T. Lane, A. Meyerson, and M. Minkoff. Approximation Algorithms for Orienteering and Discounted-Reward TSP. SIAM J. on Computing, 37(2):653--670, 2007.
[10]
A. Blum, R. Ravi and S., Vempala. A Constant-factor Approximation Algorithm for the k-MST Problem. JCSS, 58:101--108, 1999.
[11]
K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar. Paths, trees, and minimum latency tours. Proc. of IEEE FOCS, 36--45, 2003.
[12]
C. Chekuri and N. Korula. Approximation Algorithms for Orienteering with Time Windows. Manuscript, Sept. 2007.
[13]
C. Chekuri and A. Kumar. Maximum Coverage Problem with Group Budget Constraints and Applications. Proc. of APPROX-RANDOM, LNCS, 72--83, 2004.
[14]
C. Chekuri and M. Pal. A Recursive Greedy Algorithm for Walks in Directed Graphs. Proc. of IEEE FOCS, 245--253, 2005.
[15]
C. Chekuri and M. Pal. An O(log n) Approximation for the Asymmetric Traveling Salesman Path Problem. Proc. of APPROX, 95--103, 2005.
[16]
K. Chen and S. Har-Peled. The Orienteering Problem in the Plane Revisited. Proc. of ACM SoCG, 247--254, 2006.
[17]
A. Frieze, G. Galbiati and M. Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12, 23--39, 1992.
[18]
N. Garg. Saving an ε: A 2-approximation for the k-MST problem in graphs. Proc. of ACM STOC, 396--402, 2005.
[19]
N. Garg. A 3-approximation for the minimum tree spanning k vertices. Proc. of IEEE FOCS, 302--309, 1996.
[20]
M. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM J. on Computing, 24:296--317, 1995.
[21]
B. Golden, L. Levy and R. Vohra. The orienteering problem. Naval Research Logistics, 34:307--318, 1987.
[22]
G. Gutin and A. P. Punnen (Eds.). Traveling Salesman Problem and Its Variations. Springer, Berlin, 2002.
[23]
H. Kaplan, M. Lewenstein, N. Shafir and M. Sviridenko. Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multidigraphs. Journal of ACM vol. 52, 602--626, 2005.
[24]
J. Kleinberg and D. Williamson. Unpublished note, 1998.
[25]
E. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. Shmoys (Eds.). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons Ltd., 1985.
[26]
V. Nagarajan and R. Ravi. Poly-logarithmic approximation algorithms for Directed Vehicle Routing Problems. Proc. of APPROX, 257--270, 2007.
[27]
P. Toth and D. Vigo eds. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002.
[28]
J. Tsitsiklis. Special Cases of Traveling Salesman and Repairman Problems with Time Windows. Networks, vol 22, 263--282, 1992.

Cited By

View all
  • (2016)Algorithms and adaptivity gaps for stochastic probingProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884555(1731-1747)Online publication date: 10-Jan-2016
  • (2016)Approximation Algorithms for Movement RepairmenACM Transactions on Algorithms10.1145/290873712:4(1-38)Online publication date: 3-Aug-2016
  • (2015)An arc orienteering algorithm to find the most scenic path on a large-scale road networkProceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2820783.2820835(1-10)Online publication date: 3-Nov-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Algorithms and adaptivity gaps for stochastic probingProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884555(1731-1747)Online publication date: 10-Jan-2016
  • (2016)Approximation Algorithms for Movement RepairmenACM Transactions on Algorithms10.1145/290873712:4(1-38)Online publication date: 3-Aug-2016
  • (2015)An arc orienteering algorithm to find the most scenic path on a large-scale road networkProceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2820783.2820835(1-10)Online publication date: 3-Nov-2015
  • (2014)Efficient itinerary planning with category constraintsProceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2666310.2666411(203-212)Online publication date: 4-Nov-2014
  • (2013)Adaptive collective routing using gaussian process dynamic congestion modelsProceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2487575.2487598(704-712)Online publication date: 11-Aug-2013
  • (2013)Users plan optimization for participatory urban texture documentationGeoinformatica10.1007/s10707-012-0166-717:1(173-205)Online publication date: 1-Jan-2013
  • (2013)Approximation Algorithms for the Directed k-Tour and k-Stroll ProblemsAlgorithmica10.1007/s00453-011-9610-665:3(545-561)Online publication date: 1-Mar-2013
  • (2012)Approximation algorithms for stochastic orienteeringProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095237(1522-1538)Online publication date: 17-Jan-2012
  • (2012)Improved algorithms for orienteering and related problemsACM Transactions on Algorithms10.1145/2229163.22291678:3(1-27)Online publication date: 24-Jul-2012
  • (2011)Prize-collecting Steiner problems on planar graphsProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133115(1028-1049)Online publication date: 23-Jan-2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media