Document Open Access Logo

Towards Distributed Two-Stage Stochastic Optimization

Authors Yuval Emek, Noga Harlev, Taisuke Izumi

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.32.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

Yuval Emek
  • Technion - Israel Institute of Technology, Haifa, Israel
Noga Harlev
  • Technion - Israel Institute of Technology, Haifa, Israel
Taisuke Izumi
  • Nagoya Institute of Technology, Japan

Funding

  • Emek, Yuval: This work has been funded in part by an Israeli Ministry of Science and Technology grant number 3-13565.
  • Izumi, Taisuke: This work was supported by JST SICORP Grant Number JPMJSC1606 and JSPS KAKENHI Grant Number JP19K11824, Japan.

Cite AsGet BibTex

Yuval Emek, Noga Harlev, and Taisuke Izumi. Towards Distributed Two-Stage Stochastic Optimization. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.32

Abstract

The weighted vertex cover problem is concerned with selecting a subset of the vertices that covers a target set of edges with the objective of minimizing the total cost of the selected vertices. We consider a variant of this classic combinatorial optimization problem where the target edge set is not fully known; rather, it is characterized by a probability distribution. Adhering to the model of two-stage stochastic optimization, the execution is divided into two stages so that in the first stage, the decision maker selects some of the vertices based on the probabilistic forecast of the target edge set. Then, in the second stage, the edges in the target set are revealed and in order to cover them, the decision maker can augment the vertex subset selected in the first stage with additional vertices. However, in the second stage, the vertex cost increases by some inflation factor, so the second stage selection becomes more expensive. The current paper studies the two-stage stochastic vertex cover problem in the realm of distributed graph algorithms, where the decision making process (in both stages) is distributed among the vertices of the graph. By combining the stochastic optimization toolbox with recent advances in distributed algorithms for weighted vertex cover, we develop an algorithm that runs in time O(log (Δ) / ε), sends O(m) messages in total, and guarantees to approximate the optimal solution within a (3 + ε)-ratio, where m is the number of edges in the graph, Δ is its maximum degree, and 0 < ε < 1 is a performance parameter.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • weighted vertex cover
  • distributed graph algorithms
  • two-stage stochastic optimization
  • primal-dual

Metrics

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

References

  1. Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. In International Symposium on Distributed Computing, pages 191-205. Springer, 2009. Google Scholar
  2. Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures, pages 294-302. ACM, 2010. Google Scholar
  3. Ilke Bakir, Natashia Boland, Brian Dandurand, and Alan Erera. Scenario set partition dual bounds for multistage stochastic programming: A hierarchy of bounds and a partition sampling approach. Optimization Online, 2016. Google Scholar
  4. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A Distributed (2+ ε)-Approximation for Vertex Cover in O (log Δ/ε log log Δ) Rounds. Journal of the ACM (JACM), 64(3):23, 2017. Google Scholar
  5. Reuven Bar-Yehuda and Shimon Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2):198-203, 1981. Google Scholar
  6. Reuven Bar-Yehuda and Shimon Even. A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem. In North-Holland Mathematics Studies, volume 109, pages 27-45. Elsevier, 1985. Google Scholar
  7. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM (JACM), 63(3):20, 2016. Google Scholar
  8. Evelyn ML Beale. On minimizing a convex function subject to linear inequalities. Journal of the Royal Statistical Society. Series B (Methodological), pages 173-184, 1955. Google Scholar
  9. Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman. A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log N log Delta /log^2 log Delta) Rounds. In International Colloquium on Structural Information and Communication Complexity, pages 226-236. Springer, 2018. Google Scholar
  10. John R Birge and Francois Louveaux. Introduction to stochastic programming. Springer Science & Business Media, 2011. Google Scholar
  11. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. Google Scholar
  12. George B Dantzig. LINEAR PROGRAMMING UNDER UNCERTAINTY. Science, 1955. Google Scholar
  13. Kedar Dhamdhere, Vineet Goyal, R Ravi, and Mohit Singh. How to pay, come what may: Approximation algorithms for demand-robust covering problems. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 367-376. IEEE, 2005. Google Scholar
  14. Shane Dye, Leen Stougie, and Asgeir Tomasgard. The stochastic single resource service-provision problem. Naval Research Logistics (NRL), 50(8):869-887, 2003. Google Scholar
  15. Uriel Feige, Kamal Jain, Mohammad Mahdian, and Vahab Mirrokni. Robust combinatorial optimization with exponential scenarios. In International Conference on Integer Programming and Combinatorial Optimization, pages 439-453. Springer, 2007. Google Scholar
  16. Manuela Fischer. Improved Deterministic Distributed Matching via Rounding. In 31st International Symposium on Distributed Computing, DISC, pages 17:1-17:15, 2017. Google Scholar
  17. Fabrizio Grandoni, Jochen Könemann, and Alessandro Panconesi. Distributed weighted vertex cover via maximal matchings. ACM Transactions on Algorithms (TALG), 5(1):6, 2008. Google Scholar
  18. Anupam Gupta, Martin Pál, R Ravi, and Amitabh Sinha. Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems. SIAM Journal on Computing, 40(5):1361-1401, 2011. Google Scholar
  19. Anupam Gupta, R Ravi, and Amitabh Sinha. LP rounding approximation algorithms for stochastic network design. Mathematics of Operations Research, 32(2):345-364, 2007. Google Scholar
  20. Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. SIAM Journal on Discrete Mathematics, 15(1):41-57, 2001. Google Scholar
  21. Nicole Immorlica, David Karger, Maria Minkoff, and Vahab S Mirrokni. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 691-700. Society for Industrial and Applied Mathematics, 2004. Google Scholar
  22. Amos Israeli and Alon Itai. A Fast and Simple Randomized Parallel Algorithm for Maximal Matching. Inf. Process. Lett., 22(2):77-80, 1986. Google Scholar
  23. George Karakostas. A better approximation ratio for the vertex cover problem. ACM Transactions on Algorithms (TALG), 5(4):41, 2009. Google Scholar
  24. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  25. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  26. Samir Khuller, Uzi Vishkin, and Neal Young. A primal-dual parallel approximation technique applied to weighted set and vertex covers. Journal of Algorithms, 17(2):280-289, 1994. Google Scholar
  27. Willem K Klein Haneveld and Maarten H van der Vlerk. Stochastic integer programming: General models and algorithms. Annals of Operations Research, 85:39-57, 1999. Google Scholar
  28. Christos Koufogiannakis and Neal E Young. Distributed algorithms for covering, packing and maximum weighted matching. Distributed Computing, 24(1):45-63, 2011. Google Scholar
  29. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 980-989. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  30. George L Nemhauser and Leslie Earl Trotter. Vertex packings: structural properties and algorithms. Mathematical Programming, 8(1):232-248, 1975. Google Scholar
  31. Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed computing, 14(2):97-100, 2001. Google Scholar
  32. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 2000. URL: https://books.google.co.il/books?id=T1hFWuDi1CsC.
  33. Valentin Polishchuk and Jukka Suomela. A simple local 3-approximation algorithm for vertex cover. Information Processing Letters, 109(12):642-645, 2009. Google Scholar
  34. R Ravi and Amitabh Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Mathematical Programming, 108(1):97-114, 2006. Google Scholar
  35. Rüdiger Schultz, Leen Stougie, and Maarten H van der Vlerk. Two-stage stochastic integer programming: a survey. Statistica Neerlandica, 50(3):404-416, 1996. Google Scholar
  36. David B Shmoys and Chaitanya Swamy. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. Journal of the ACM (JACM), 53(6):978-1012, 2006. Google Scholar
  37. Aravind Srinivasan. Approximation algorithms for stochastic and risk-averse optimization. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1305-1313, 2007. Google Scholar
  38. Chaitanya Swamy and David B Shmoys. Sampling-based approximation algorithms for multi-stage stochastic optimization. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 357-366. IEEE, 2005. Google Scholar
  39. Chaitanya Swamy and David B Shmoys. Approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News, 37(1):33-46, 2006. 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