Improved algorithms for orienteering and related problems

Chandra Sekhar Chekuri, Nitish Korula, Martin Pal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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,t ∈V 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(log 2 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages661-670
Number of pages10
StatePublished - Dec 1 2008
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CitySan Francisco, CA
Period1/20/081/22/08

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Improved algorithms for orienteering and related problems'. Together they form a unique fingerprint.

Cite this