Document Open Access Logo

Algorithms and Adaptivity Gaps for Stochastic k-TSP

Authors Haotian Jiang, Jian Li, Daogao Liu, Sahil Singla

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.45.pdf
  • Filesize: 0.65 MB
  • 25 pages

Document Identifiers

Author Details

Haotian Jiang
  • Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, USA
Jian Li
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Daogao Liu
  • Department of Physics, Tsinghua University, Beijing, China
Sahil Singla
  • Princeton University and Institute for Advanced Study, Princeton, USA

Acknowledgements

We are thankful to the anonymous reviewers of ITCS 2020 for many helpful comments on the presentation of this paper. Haotian Jiang is supported in part by NSF awards CCF-1749609, CCF-1740551 and DMS-1839116. Jian Li and Daogao Liu are supported in part by the National Natural Science Foundation of China Grant 61822203, 61772297, 61632016, 61761146003, and the Zhongguancun Haihua Institute for Frontier Information Technology and Turing AI Institute of Nanjing. Sahil Singla is supported in part by the Schmidt Foundation.

Cite AsGet BibTex

Haotian Jiang, Jian Li, Daogao Liu, and Sahil Singla. Algorithms and Adaptivity Gaps for Stochastic k-TSP. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 45:1-45:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.45

Abstract

Given a metric (V,d) and a root ∈ V, the classic k-TSP problem is to find a tour originating at the root of minimum length that visits at least k nodes in V. In this work, motivated by applications where the input to an optimization problem is uncertain, we study two stochastic versions of k-TSP. In Stoch-Reward k-TSP, originally defined by Ene-Nagarajan-Saket [Ene et al., 2018], each vertex v in the given metric (V,d) contains a stochastic reward R_v. The goal is to adaptively find a tour of minimum expected length that collects at least reward k; here "adaptively" means our next decision may depend on previous outcomes. Ene et al. give an O(log k)-approximation adaptive algorithm for this problem, and left open if there is an O(1)-approximation algorithm. We totally resolve their open question, and even give an O(1)-approximation non-adaptive algorithm for Stoch-Reward k-TSP. We also introduce and obtain similar results for the Stoch-Cost k-TSP problem. In this problem each vertex v has a stochastic cost C_v, and the goal is to visit and select at least k vertices to minimize the expected sum of tour length and cost of selected vertices. Besides being a natural stochastic generalization of k-TSP, this problem is also interesting because it generalizes the Price of Information framework [Singla, 2018] from deterministic probing costs to metric probing costs. Our techniques are based on two crucial ideas: "repetitions" and "critical scaling". In general, replacing a random variable with its expectation leads to very poor results. We show that for our problems, if we truncate the random variables at an ideal threshold, then their expected values form a good surrogate. Here, we rely on running several repetitions of our algorithm with the same threshold, and then argue concentration using Freedman’s and Jogdeo-Samuels' inequalities. Unfortunately, this ideal threshold depends on how far we are from achieving our target k, which a non-adaptive algorithm does not know. To overcome this barrier, we truncate the random variables at various different scales and identify a "critical" scale.

Subject Classification

ACM Subject Classification
  • Theory of computation → Stochastic control and optimization
  • Theory of computation → Approximation algorithms analysis
Keywords
  • approximation algorithms
  • stochastic optimization
  • travelling salesman problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora and George Karakostas. 2+ ε approximation algorithm for the k-MST problem. In 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 754-759. SIAM, 2000. Google Scholar
  2. Sunil Arya and Hariharan Ramesh. A 2.5-factor approximation algorithm for the k-MST problem. Information Processing Letters, 65(3):117-118, 1998. Google Scholar
  3. Arash Asadpour and Hamid Nazerzadeh. Maximizing stochastic monotone submodular functions. Management Science, 62(8):2374-2391, 2016. Google Scholar
  4. Baruch Awerbuch, Yossi Azar, Avrim Blum, and Santosh Vempala. New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen. SIAM J. Comput., 28(1):254-262, 1998. Google Scholar
  5. Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra. When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Algorithmica, 63(4):733-762, 2012. Google Scholar
  6. Nikhil Bansal and Viswanath Nagarajan. On the Adaptivity Gap of Stochastic Orienteering. In IPCO, pages 114-125, 2014. Google Scholar
  7. Anand Bhalgat, Ashish Goel, and Sanjeev Khanna. Improved Approximation Results for Stochastic Knapsack Problems. In SODA, pages 1647-1665, 2011. Google Scholar
  8. Avrim Blum, R. Ravi, and Santosh Vempala. A Constant-factor Approximation Algorithm for the k Problem (Extended Abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 442-448, 1996. Google Scholar
  9. Domagoj Bradac, Sahil Singla, and Goran Zuzic. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 49:1-49:21, 2019. Google Scholar
  10. Chandra Chekuri, Nitish Korula, and Martin Pál. Improved algorithms for orienteering and related problems. ACM Transactions on Algorithms (TALG), 8(3):23, 2012. Google Scholar
  11. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 208-217. IEEE, 2004. Google Scholar
  12. Amol Deshpande, Lisa Hellerstein, and Devorah Kletenik. Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack. ACM Trans. Algorithms, 12(3):42:1-42:28, 2016. Google Scholar
  13. Alina Ene, Viswanath Nagarajan, and Rishi Saket. Approximation Algorithms for Stochastic k-TSP. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  14. David A Freedman. On tail probabilities for martingales. the Annals of Probability, 3(1):100-118, 1975. Google Scholar
  15. Hao Fu, Jian Li, and Pan Xu. A PTAS for a Class of Stochastic Dynamic Programs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  16. N. Garg. A 3-approximation for the Minimum Tree Spanning K Vertices. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS '96, pages 302-, 1996. Google Scholar
  17. Naveen Garg. Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 396-402. ACM, 2005. Google Scholar
  18. Michel X. Goemans and Jan Vondrák. Stochastic Covering and Adaptivity. In LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Proceedings, pages 532-543, 2006. Google Scholar
  19. Sudipto Guha and Kamesh Munagala. Multi-armed Bandits with Metric Switching Costs. In ICALP, pages 496-507, 2009. Google Scholar
  20. Sudipto Guha and Kamesh Munagala. Adaptive uncertainty resolution in bayesian combinatorial optimization problems. ACM Transactions on Algorithms (TALG), 8(1):1, 2012. Google Scholar
  21. Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla. The Markovian Price of Information. In Integer Programming and Combinatorial Optimization, IPCO, pages 233-246, 2019. Google Scholar
  22. Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, and R. Ravi. Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits. In FOCS, pages 827-836, 2011. Google Scholar
  23. Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, and R. Ravi. Approximation Algorithms for Stochastic Orienteering. In SODA, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095237.
  24. Anupam Gupta and Viswanath Nagarajan. A Stochastic Probing Problem with Applications. In IPCO, pages 205-216, 2013. Google Scholar
  25. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1688-1702. SIAM, 2017. Google Scholar
  26. Zhihao Jiang and Haoyu Zhao. An FPTAS for Stochastic Unbounded Min-Knapsack Problem. In International Workshop on Frontiers in Algorithmics, pages 121-132. Springer, 2019. Google Scholar
  27. Kumar Jogdeo and Stephen M Samuels. Monotone convergence of binomial probabilities and a generalization of Ramanujan’s equation. The Annals of Mathematical Statistics, 39(4):1191-1195, 1968. Google Scholar
  28. Robert Kleinberg, Bo Waggoner, and Glen Weyl. Descending Price Optimally Coordinates Search. arXiv preprint, 2016. URL: http://arxiv.org/abs/1603.07682.
  29. Will Ma. Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract. In SODA, pages 1154-1163, 2014. Google Scholar
  30. Sridhar Rajagopalan and V Vazirani. Logarithmic approximation of minimum weight k trees. Unpublished manuscript, 1995. Google Scholar
  31. Ramamurthy Ravi, Ravi Sundaram, Madhav V Marathe, Daniel J Rosenkrantz, and Sekharipuram S Ravi. Spanning trees-short or small. SIAM Journal on Discrete Mathematics, 9(2):178-200, 1996. Google Scholar
  32. Sahil Singla. Combinatorial Optimization Under Uncertainty: Probing and Stopping-Time Algorithms. PhD thesis, Carnegie Mellon University, 2018. Google Scholar
  33. Sahil Singla. The Price of Information in Combinatorial Optimization. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2018. Google Scholar
  34. Martin L. Weitzman. Optimal search for the best alternative. Econometrica: Journal of the Econometric Society, pages 641-654, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact