Document Open Access Logo

Approximation Algorithms for Stochastic k-TSP

Authors Alina Ene, Viswanath Nagarajan, Rishi Saket

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.27.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Alina Ene
Viswanath Nagarajan
Rishi Saket

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.27

Abstract

This paper studies the stochastic variant of the classical k-TSP problem where rewards at the vertices are independent random variables which are instantiated upon the tour's visit. The objective is to minimize the expected length of a tour that collects reward at least k. The solution is a policy describing the tour which may (adaptive) or may not (non-adaptive) depend on the observed rewards. 
Our work presents an adaptive O(log k)-approximation algorithm for Stochastic k-TSP, along with a non-adaptive O(log^2 k)-approximation algorithm which also upper bounds the adaptivity gap by O(log^2 k). We also show that the adaptivity gap of Stochastic k-TSP  is at least e, even in the special case of stochastic knapsack cover.

Subject Classification

Keywords
  • Stochastic TSP
  • algorithms
  • approximation
  • adaptivity gap

Metrics

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

References

  1. M. Adamczyk. Improved analysis of the greedy algorithm for stochastic matching. Information Processing Letters, 111(15):731-737, 2011. Google Scholar
  2. M. Adamczyk, F. Grandoni, and J. Mukherjee. Improved approximation algorithms for stochastic matching. In Proc. Annual European Symposium on Algorithms, pages 1-12, 2015. Google Scholar
  3. M. Adamczyk, M. Sviridenko, and J. Ward. Submodular stochastic probing on matroids. Math. Oper. Res., 41(3):1022-1038, 2016. Google Scholar
  4. Y. Azar, A. Madry, T. Moscibroda, D. Panigrahi, and A. Srinivasan. Maximum bipartite flow in networks with adaptive channel width. Theoretical Computer Science, 412(24):2577-2587, 2011. Google Scholar
  5. N. Bansal, A. Gupta, J. Li, J. Mestre, V. Nagarajan, and A. Rudra. When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica, 63(4):733-762, 2012. Google Scholar
  6. N. Bansal and V. Nagarajan. On the adaptivity gap of stochastic orienteering. Mathematical Programming, 154(1-2):145-172, 2015. Google Scholar
  7. A. Baveja, A. Chavan, A. Nikiforov, A. Srinivasan, and P. Xu. Improved bounds in stochastic matching and optimization. In Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 124-134, 2015. Google Scholar
  8. A. Bhalgat, A. Goel, and S. Khanna. Improved approximation results for stochastic knapsack problems. In Proc. Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1647-1665. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  9. A. Blum, S. Chawla, D. R. Karger, T. Lane, A. Meyerson, and M. Minkoff. Approximation algorithms for orienteering and discounted-reward TSP. SIAM Journal of Computing, 37(2):653-670, 2007. Google Scholar
  10. K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar. Paths, trees, and minimum latency tours. In Proc. Annual Symposium on Foundations of Computer Science, pages 36-45, 2003. Google Scholar
  11. C. Chekuri, N. Korula, and M. Pál. Improved algorithms for orienteering and related problems. ACM Transactions on Algorithms, 8(3):23, 2012. Google Scholar
  12. N. Chen, N. Immorlica, A. R Karlin, M. Mahdian, and A. Rudra. Approximating matches made in heaven. In Proc. International Colloquium on Automata, Languages and Programming, pages 266-278. Springer, 2009. Google Scholar
  13. M. Chrobak, C. Kenyon, J. Noga, and N. E. Young. Incremental medians via online bidding. Algorithmica, 50(4):455-478, 2008. Google Scholar
  14. B. C Dean, M. X. Goemans, and J. Vondrák. Adaptivity and approximation for stochastic packing problems. In Proc. Annual ACM-SIAM Symposium on Discrete Algorithms, pages 395-404. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  15. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res., 33(4):945-964, 2008. URL: http://dx.doi.org/10.1287/moor.1080.0330.
  16. A. Deshpande, L. Hellerstein, and D. Kletenik. Approximation algorithms for stochastic submodular set cover with applications to boolean function evaluation and min-knapsack. ACM Transactions on Algorithms, 12(3):42, 2016. Google Scholar
  17. J. Fakcharoenphol, C. Harrelson, and S. Rao. The k-traveling repairmen problem. ACM Transactions on Algorithms, 3(4), 2007. Google Scholar
  18. N. Garg. Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In Proc. ACM Symposium on the Theory of Computing, pages 396-402, 2005. Google Scholar
  19. M. X. Goemans and Jan Vondrák. Stochastic covering and adaptivity. In Proc. Latin American Symposium on Theoretical Informatics(LATIN), pages 532-543, 2006. Google Scholar
  20. D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486, 2011. Google Scholar
  21. N. Grammel, L. Hellerstein, D. Kletenik, and P. Lin. Scenario submodular cover. In International Workshop on Approximation and Online Algorithms, pages 116-128. Springer, 2016. Google Scholar
  22. S. Guha and K. Munagala. Multi-armed bandits with metric switching costs. Automata, Languages and Programming, pages 496-507, 2009. Google Scholar
  23. A. Gupta, R. Krishnaswamy, M. Molinaro, and R. Ravi. Approximation algorithms for correlated knapsacks and non-martingale bandits. In Proc. Annual Symposium on Foundations of Computer Science, pages 827-836, 2011. Google Scholar
  24. A. Gupta, R. Krishnaswamy, V. Nagarajan, and R. Ravi. Running errands in time: Approximation algorithms for stochastic orienteering. Math. Oper. Res., 40(1):56-79, 2015. Google Scholar
  25. A. Gupta and V. Nagarajan. A stochastic probing problem with applications. In Proc. Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 205-216, 2013. Google Scholar
  26. A. Gupta, V. Nagarajan, and S. Singla. Adaptivity gaps for stochastic probing: Submodular and XOS functions. In Proc. Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1688-1702, 2017. Google Scholar
  27. Sungjin Im, Viswanath Nagarajan, and Ruben van der Zwaan. Minimum latency submodular cover. ACM Trans. Algorithms, 13(1):13:1-13:28, 2016. Google Scholar
  28. P. Kambadur, V. Nagarajan, and F. Navidi. Adaptive submodular ranking. In Proc. Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 317-329, 2017. Google Scholar
  29. G. Lin, C. Nagarajan, R. Rajaraman, and D. P. Williamson. A general approach for incremental approximation and hierarchical clustering. SIAM Journal of Computing, 39(8):3633-3669, 2010. Google Scholar
  30. W. Ma. Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms. In Proc. Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1154-1163. Society for Industrial and Applied Mathematics, 2014. 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 About DROPS Imprint Privacy Contact