TY - GEN

T1 - Improved algorithms for orienteering and related problems

AU - Chekuri, Chandra Sekhar

AU - Korula, Nitish

AU - Pal, Martin

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=58649112596&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58649112596&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58649112596

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 661

EP - 670

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -