Document Open Access Logo

Approximating Two-Stage Stochastic Supplier Problems

Authors Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.23.pdf
  • Filesize: 0.8 MB
  • 22 pages

Document Identifiers

Author Details

Brian Brubach
  • Wellesley College, MA, USA
Nathaniel Grammel
  • University of Maryland at College Park, MD, USA
David G. Harris
  • University of Maryland at College Park, MD, USA
Aravind Srinivasan
  • University of Maryland at College Park, MD, USA
Leonidas Tsepenekas
  • University of Maryland at College Park, MD, USA
Anil Vullikanti
  • University of Virginia, Charlottesville, VA, USA

Funding

  • Brubach, Brian: Brian Brubach was supported in part by NSF awards CCF-1422569 and CCF-1749864, and by research awards from Adobe.
  • Grammel, Nathaniel: Nathaniel Grammel was supported in part by NSF awards CCF-1749864 and CCF-1918749, and by research awards from Amazon and Google.
  • Srinivasan, Aravind: Aravind Srinivasan was supported in part by NSF awards CCF-1422569, CCF-1749864 and CCF-1918749, and by research awards from Adobe, Amazon, and Google.
  • Tsepenekas, Leonidas: Leonidas Tsepenekas was supported in part by NSF awards CCF-1749864 and CCF-1918749, and by research awards from Amazon and Google.

Acknowledgements

The authors want to sincerely thank Chaitanya Swamy as well as referees of earlier versions of the paper, for their precious feedback and helpful suggestions.

Cite As Get BibTex

Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, and Anil Vullikanti. Approximating Two-Stage Stochastic Supplier Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.23

Abstract

The main focus of this paper is radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the form of a budget constraint. We also explore a number of variants where additional constraints are imposed on the first-stage decisions, specifically matroid and multi-knapsack constraints. 
Our eventual goal is to provide results for supplier problems in the most general distributional setting, where there is only black-box access to the underlying distribution. To that end, we follow a two-step approach. First, we develop algorithms for a restricted version of each problem, in which all possible scenarios are explicitly provided; second, we employ a novel scenario-discarding variant of the standard Sample Average Approximation (SAA) method, in which we crucially exploit properties of the restricted-case algorithms. We finally note that the scenario-discarding modification to the SAA method is necessary in order to optimize over the radius.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Approximation Algorithms
  • Stochastic Optimization
  • Two-Stage Recourse Model
  • Clustering Problems
  • Knapsack Supplier

Metrics

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

Related Versions

References

  1. Shipra Agrawal, Amin Saberi, and Yinyu Ye. Stochastic combinatorial optimization under probabilistic constraints, 2008. URL: http://arxiv.org/abs/0809.0460.
  2. E. M. L. 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
  3. Deeparnab Chakrabarty and Maryam Negahbani. Generalized center problems with outliers. ACM Trans. Algorithms, 2019. Google Scholar
  4. Moses Charikar, Chandra Chekuri, and Martin Pal. Sampling bounds for stochastic optimization. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 257-269, 2005. Google Scholar
  5. George B. Dantzig. Linear programming under uncertainty. Management Science, pages 197-206, 1955. Google Scholar
  6. Uriel Feige. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM Journal on Computing, 35(4):964-984, 2006. Google Scholar
  7. A. Gupta, R. Ravi, and A. Sinha. An edge in time saves nine: Lp rounding approximation algorithms for stochastic network design. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 218-227, 2004. Google Scholar
  8. Anupam Gupta, Martin Pál, R. Ravi, and Amitabh Sinha. Boosted sampling: Approximation algorithms for stochastic optimization. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC '04, page 417–426, 2004. Google Scholar
  9. Anupam Gupta, Martin Pal, R. Ravi, and Amitabh Sinha. Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems. SIAM J. Comput., pages 1361-1401, 2011. Google Scholar
  10. Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. J. ACM, 1986. Google Scholar
  11. 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, 2004. Google Scholar
  12. Anton J. Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2):479-502, 2002. Google Scholar
  13. Lap-Chi Lau, R. Ravi, and Mohit Singh. Iterative Methods in Combinatorial Optimization. Cambridge University Press, USA, 1st edition, 2011. Google Scholar
  14. Andre Linhares and Chaitanya Swamy. Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 768-779, 2019. Google Scholar
  15. Andrea Pietracaprina, Geppino Pucci, and Federico Solda. Coreset-based strategies for robust center-type problems, 2020. URL: http://arxiv.org/abs/2002.07463.
  16. R. Ravi and Amitabh Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In Integer Programming and Combinatorial Optimization, 2004. Google Scholar
  17. David Shmoys and Chaitanya Swamy. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM, 53:978-1012, November 2006. Google Scholar
  18. Aravind Srinivasan. Approximation algorithms for stochastic and risk-averse optimization. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1305-1313, 2007. Google Scholar
  19. C. Swamy and D. B. Shmoys. Sampling-based approximation algorithms for multi-stage stochastic optimization. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 357-366, 2005. Google Scholar
  20. Chaitanya Swamy. Risk-averse stochastic optimization: Probabilistically-constrained models and algorithms for black-box distributions: (extended abstract). Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1627-1646, 2011. Google Scholar
  21. Chaitanya Swamy and David Shmoys. The sample average approximation method for 2-stage stochastic optimization. Survey Paper, April 2008. Google Scholar
  22. Chaitanya Swamy and David B. Shmoys. Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News, pages 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 About DROPS Imprint Privacy Contact