A recursive greedy algorithm for walks in directed graphs

Chandra Chekuri, Martin Pál

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

Abstract

Given an arc-weighted directed graph G = (V, A, ℓ) and a pair of nodes s,t, we seek to find an s-t walk of length at most B that maximizes some given function f of the set of nodes visited by the walk. The simplest case is when we seek to maximize the number of nodes visited: this is called the orienteering problem. Our main result is a quasi-polynomial time algorithm that yields an O (log OPT) approximation for this problem when f is a given submodular set function. We then extend it to the case when a node v is counted as visited only if the walk reaches v in its time window [R(v),D(v]. We apply the algorithm to obtain several new results. First, we obtain an O(log OPT) approximation for a generalization of the orienteering problem in which the profit for visiting each node may vary arbitrarily with time. This captures the time window problem considered earlier for which, even in undirected graphs, the best approximation ratio known [4] is O(log 2 OPT). The second application is an O(log 2 fc) approximation for the k-TSP problem in directed graphs (satisfying asymmetric triangle inequality). This is the first non-trivial approximation algorithm for this problem. The third application is an O(log 2 fc) approximation (in quasi-poly time) for the group Steiner problem in undirected graphs where k is the number of groups. This improves earlier ratios [15, 19, 8] by a logarithmic factor and almost matches the inapproximability threshold on trees [20]. This connection to group Steiner trees also enables us to prove that the problem we consider is hard to approximate to a ratio better than Ω(log 1-ε OPT), even in undirected graphs. Even though our algorithm runs in quasi-poly time, we believe that the implications for the approximability of several basic optimization problems are interesting.

Original languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages245-253
Number of pages9
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2005
ISSN (Print)0272-5428

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'A recursive greedy algorithm for walks in directed graphs'. Together they form a unique fingerprint.

Cite this