More Web Proxy on the site http://driver.im/

Article

A Recursive Greedy Algorithm for Walks in Directed Graphs

Authors:

Chandra Chekuri,

Martin PalAuthors Info & Claims

FOCS '05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science

Pages 245 - 253

https://doi.org/10.1109/SFCS.2005.9

Published: 23 October 2005 Publication History

Abstract

Given an arc-weighted directed graph G = (V, A, \ell) 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 quasipolynomial 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 k) 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 k) 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 \Omega(\log^{1 - \varepsilon} OPT), even in undirected graphs.

References

[1]

E. Arkin, J. Mitchell, and G. Narasimhan. Resource-constrained geometric network optimization. Proc. of ACM SoCG , 307-316, 1998.

[2]

S. Arora and G. Karakostas. A 2 + ¿ approximation algorithm for the k-mst problem. Proc. of ACM-SIAM SODA , 754-759, 2000.

[3]

E. Balas. The prize collecting traveling salesman problem. Networks , 19:621-636, 1989.

[4]

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.

[5]

A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor and B. Schieber. A unified approach to approximating resource allocation and scheduling. JACM , 48(5): 1069- 1090, 2001.

[6]

R. Bar-Yehuda, G. Even and S. Shahar. On Approximating a Geometric Prize-Collecting Traveling Salesman Problem with Time Windows. To appear in J. of Algorithms . Preliminary version in Proc. of ESA , 55- 66, 2003.

[7]

A. Blum, S. Chawla, D. Karger, T. Lane, A. Meyerson, and M. Minkoff. Approximation Algorithms for Orienteering and Discounted-Reward TSP. Proc. of IEEE FOCS , 46-55, 2003.

[8]

M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha and M. Li. Approximation Algorithms for Directed Steiner Problems. J. of Algorithms , 33, p. 73-91, 1999.

[9]

C. Chekuri, G. Even, and G. Kortsarz. A greedy approximation algorithm for the group Steiner problem. To appear in Discrete Applied Math . Manuscript 2002.

[10]

C. Chekuri and A. Kumar. Maximum Coverage Problem with Group Budget Constraints and Applications. Proc. of APPROX-RANDOM , LNCS, 72-83, 2004.

[11]

G. Even, G. Kortsarz and W. Slany. On network design problems: fixed cost flows and the covering Steiner problem. Proc. of SWAT , LNCS, 318-327, 2002.

[12]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Proc. of ACM STOC , 448-455, 2003.

[13]

A. Frieze, G. Galbiati and M. Maffioli. On the worstcase performance of some algorithms for the asymmetric traveling salesman problem. Networks 12, 23- 39, 1992.

[14]

N. Garg. Saving an ¿: A 2-approximation for the k - MST problem in graphs. Proc. of ACM STOC , 396- 402, 2005.

[15]

N. Garg and G. Konjevod and R. Ravi, A polylogarithmic approximation algorithm for the Group Steiner tree problem. J. of Algorithms , 37, 66-84, 2000. Preliminary version in Proc. of ACM-SIAM SODA , 1998.

[16]

M. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM J. on Computing , 24:296-317, 1995.

[17]

B. Golden, L. Levy and R. Vohra. The orienteering problem. Naval Research Logistics , 34:307-318, 1987.

[18]

A. Gupta and A. Srinivasan. On the Covering Steiner Problem. Proc. of FST&TCS LNCS, 244-251, 2003.

[19]

E. Halperin, G. Kortsarz, R. Krauthgamer, A. Srinivasan and N. Wang. Integrality ratio for Group Steiner Trees and Directed Steiner Trees. Proc. of ACM-SIAM SODA , 275-284, 2003.

[20]

E. Halperin and R. Krauthgamer. Polylogarithmic In-approximability. Proc. of ACM STOC , 585-594, 2003.

[21]

C. H. Helvig, G. Robins, and A. Zelikovsky. Improved approximation scheme for the group Steiner problem. Networks , 37(1):8-20, 2001.

[22]

H. Kaplan, M. Lewenstein, N. Shafir and M. Sviridenko. Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multidigraphs. Proc. of IEEE FOCS , 56-67, 2003.

[23]

G. Konjevod, R. Ravi and A. Srinivasan. Approximation Algorithms for the Covering Steiner Problem. Random Structures & Algorithms , vol. 20, 465-482, 2002.

[24]

Walter J. Savitch. Relatioships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci. , 4(2):177-192, 1970.

[25]

The Vehicle Routing Problem P. Toth, D. Vigo eds, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002.

[26]

J. Tsitsiklis. Special Cases of Traveling Salesman and Repairman Problems with Time Windows. Networks , vol. 22, 263-282, 1992.

[27]

A. Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica , 18: 99-110, 1997.

Cited By

De Santi RPrajapat MKrause ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Global reinforcement learningProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692478(10235-10266)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692478
Do AGuo MNeumann ANeumann FElkind E(2023)Diverse approximations for monotone submodular maximization problems with a matroid constraintProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/617(5558-5566)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/617
Matloob SDutta AKreidl PTurgut DBölöni LBoukerche ADe Rango FSun Z(2023)Exploring the Tradeoffs Between Systematic and Random Exploration in Mobile SensorsProceedings of the Int'l ACM Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems10.1145/3616388.3617524(209-216)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3616388.3617524
Show More Cited By

Index Terms

A Recursive Greedy Algorithm for Walks in Directed Graphs
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
      2. Game tree search
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Paths and connectivity problems

Recommendations

Greedy approximation algorithms for directed multicuts

The Directed Multicut (DM) problem is: given a simple directed graph G = (V, E) with positive capacities u_e on the edges, and a set K ⊆ V × V of ordered pairs of nodes of G, find a minimum capacity K-multicut; C ⊆ E is a K-multicut if in G - C there is ...
On Mergings in Acyclic Directed Graphs

Consider an acyclic directed graph $G$ with sources $s_1, s_2, \ldots,s_n$ and sinks $r_1, r_2, \ldots, r_n$. For $i=1, 2, \ldots,n$, let $c_i$ denote the size of the minimum edge cut between $s_i$ and $r_i$, which, by Menger's theorem, implies that there ...
Analysis of a randomized greedy matching algorithm

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FOCS '05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science

October 2005

645 pages

ISBN:0769524680

Publisher

IEEE Computer Society

United States

Publication History

Published: 23 October 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

De Santi RPrajapat MKrause ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Global reinforcement learningProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692478(10235-10266)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692478
Do AGuo MNeumann ANeumann FElkind E(2023)Diverse approximations for monotone submodular maximization problems with a matroid constraintProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/617(5558-5566)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/617
Matloob SDutta AKreidl PTurgut DBölöni LBoukerche ADe Rango FSun Z(2023)Exploring the Tradeoffs Between Systematic and Random Exploration in Mobile SensorsProceedings of the Int'l ACM Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems10.1145/3616388.3617524(209-216)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3616388.3617524
Shi GZhou LTokekar P(2023)Robust Multiple-Path Orienteering Problem: Securing Against Adversarial AttacksIEEE Transactions on Robotics10.1109/TRO.2022.323226839:3(2060-2077)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TRO.2022.3232268
Garg NKhanna SKumar AMarx D(2021)Hardness of approximation for orienteering with multiple time windowsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458241(2977-2990)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458241
Sun YXiao XCui BHalgamuge SLappas TLuo J(2021)Finding group Steiner trees in graphs with both vertex and edge weightsProceedings of the VLDB Endowment10.14778/3450980.345098214:7(1137-1149)Online publication date: 12-Apr-2021
https://dl.acm.org/doi/10.14778/3450980.3450982
Périvier NHssaine CSamaranayake SBanerjee S(2021)Real-time Approximate Routing for Smart Transit SystemsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34600915:2(1-30)Online publication date: 4-Jun-2021
https://dl.acm.org/doi/10.1145/3460091
Grandoni FLaekhanukit BLi SCharikar MCohen E(2019)O(log2 k / log log k)-approximation algorithm for directed Steiner treeProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316349(253-264)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316349
Corah MMichael N(2019)Distributed matroid-constrained submodular maximization for multi-robot explorationAutonomous Robots10.1007/s10514-018-9778-643:2(485-501)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10514-018-9778-6
Hepp BNießner MHilliges O(2018)Plan3DACM Transactions on Graphics10.1145/323379438:1(1-17)Online publication date: 14-Dec-2018
https://dl.acm.org/doi/10.1145/3233794
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents