Document Open Access Logo

Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty

Authors David Ellis Hershkowitz, R. Ravi, Sahil Singla

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.4.pdf
  • Filesize: 0.57 MB
  • 19 pages

Document Identifiers

Author Details

David Ellis Hershkowitz
  • Carnegie Mellon University, Pittsburgh, PA, USA
R. Ravi
  • Carnegie Mellon University, Pittsburgh, PA, USA
Sahil Singla
  • Princeton University, Princeton, NJ, USA
  • Institute for Advanced Study, Princeton, NJ, USA

Funding

  • Hershkowitz, David Ellis: Supported in part by NSF grants CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808 and a Sloan Research Fellowship.
  • Ravi, R.: Supported in part by the U. S. Office of Naval Research award N00014-18-1-2099, and the U. S. NSF award CCF-1527032.
  • Singla, Sahil: Supported in part by Schmidt Foundation and NSF awards CCF-1319811, CCF-1536002, and CCF-1617790.

Cite As Get BibTex

David Ellis Hershkowitz, R. Ravi, and Sahil Singla. Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.4

Abstract

In this paper we study how to optimally balance cheap inflexible resources with more expensive, reconfigurable resources despite uncertainty in the input problem. Specifically, we introduce the MinEMax model to study "build versus rent" problems. In our model different scenarios appear independently. Before knowing which scenarios appear, we may build rigid resources that cannot be changed for different scenarios. Once we know which scenarios appear, we are allowed to rent reconfigurable but expensive resources to use across scenarios. Although computing the objective in our model might seem to require enumerating exponentially-many possibilities, we show it is well estimated by a surrogate objective which is representable by a polynomial-size LP. In this surrogate objective we pay for each scenario only to the extent that it exceeds a certain threshold. Using this objective we design algorithms that approximately-optimally balance inflexible and reconfigurable resources for several NP-hard covering problems. For example, we study variants of minimum spanning and Steiner trees, minimum cuts, and facility location. Up to constants, our approximation guarantees match those of previously-studied algorithms for demand-robust and stochastic two-stage models. Lastly, we demonstrate that our problem is sufficiently general to smoothly interpolate between previous demand-robust and stochastic two-stage problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Packing and covering problems
  • Theory of computation → Routing and network design problems
  • Theory of computation → Facility location and clustering
  • Theory of computation → Rounding techniques
Keywords
  • Approximation Algorithms
  • Optimization Under Uncertainty
  • Two-Stage Optimization
  • Expected Max

Metrics

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

Related Versions

References

  1. Carlo Acerbi and Dirk Tasche. Expected shortfall: a natural coherent alternative to value at risk. Economic notes, 31(2):379-388, 2002. Google Scholar
  2. Shipra Agrawal, Yichuan Ding, Amin Saberi, and Yinyu Ye. Price of correlations in stochastic optimization. Operations Research, 60(1):150-162, 2012. Google Scholar
  3. Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing (SICOMP), 43(2):930-972, 2014. Google Scholar
  4. Barbara M. Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A Plant Location Guide for the Unsure. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008. Google Scholar
  5. D. Bertsimas, D. Brown, and C. Caramanis. Theory and Applications of Robust Optimization. SIAM Review, 53(3):464-501, 2011. Google Scholar
  6. Dimitris Bertsimas, Karthik Natarajan, and Chung-Piaw Teo. Probabilistic combinatorial optimization: Moments, semidefinite programming, and asymptotic bounds. SIAM Journal on Optimization, 15(1):185-209, 2004. Google Scholar
  7. Deeparnab Chakrabarty and Chaitanya Swamy. Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), pages 29:1-29:14, 2018. Google Scholar
  8. Erick Delage and Yinyu Ye. Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems. Operations Research, 58(3):595-612, 2010. Google Scholar
  9. Kedar Dhamdhere, Vineet Goyal, R. Ravi, and Mohit Singh. How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. In Proceedings of the Symposium on the Foundations of Computer Science (FOCS), pages 367-378, 2005. Google Scholar
  10. Kedar Dhamdhere, R Ravi, and Mohit Singh. On two-stage stochastic minimum spanning trees. In Proceedings of International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 321-334, 2005. Google Scholar
  11. Anulekha Dhara and Karthik Natarajan. On the polynomial solvability of distributionally robust k-sum optimization. Optimization Methods and Software, 32(4):738-753, 2017. Google Scholar
  12. Joel Goh and Melvyn Sim. Distributionally Robust Optimization and Its Tractable Approximations. Operations Research, 58(4-part-1):902-917, 2010. Google Scholar
  13. Daniel Golovin, Vineet Goyal, Valentin Polishchuk, R. Ravi, and Mikko Sysikaski. Improved approximations for two-stage min-cut and shortest path problems under uncertainty. Mathematical Programming, 149(1):167-194, February 2015. Google Scholar
  14. Anupam Gupta, Viswanath Nagarajan, and R Ravi. Thresholded covering algorithms for robust and max-min optimization. Automata, Languages and Programming, pages 262-274, 2010. Google Scholar
  15. Anupam Gupta, Martin Pal, R Ravi, and Amitabh Sinha. Boosted sampling: approximation algorithms for stochastic optimization. In Proceedings of the Symposium on the Theory of Computing (STOC), pages 417-426, 2004. Google Scholar
  16. Anupam Gupta, R Ravi, and Amitabh Sinha. An edge in time saves nine: LP rounding approximation algorithms for stochastic network design. In Proceedings of the Symposium on the Foundations of Computer Science (FOCS), pages 218-227, 2004. Google Scholar
  17. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 691-700, 2004. Google Scholar
  18. Ruiwei Jiang and Yongpei Guan. Risk-averse two-stage stochastic program with distributional ambiguity. Operations Research, 66(5):1390-1405, 2018. Google Scholar
  19. TL Lai and Herbert Robbins. Maximally dependent random variables. Proceedings of the National Academy of Sciences, 73(2):286-288, 1976. Google Scholar
  20. Andre Linhares and Chaitanya Swamy. Approximation Algorithms for Distributionally-Robust Stochastic Optimization with Black-Box Distributions. In Proceedings of the Symposium on the Theory of Computing (STOC), 2019. Google Scholar
  21. Isaac Meilijson and Arthur Nádas. Convex majorization with an application to the length of critical paths. Journal of Applied Probability, 16(3):671-677, 1979. Google Scholar
  22. R Ravi and Amitabh Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In Proceedings of International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 101-115, 2004. Google Scholar
  23. Herbert Scarf. A Min-Max Solution of an Inventory Problem. Studies in the Mathematical Theory of Inventory and Production, pages 201-209, 1958. Google Scholar
  24. 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, November 2006. Google Scholar
  25. Anthony Man-Cho So, Jiawei Zhang, and Yinyu Ye. Stochastic combinatorial optimization with controllable risk aversion level. Mathematics of Operations Research, 34(3):522-537, 2009. Google Scholar
  26. Aravind Srinivasan. Approximation algorithms for stochastic and risk-averse optimization. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1305-1313, 2007. Google Scholar
  27. Chaitanya Swamy. Risk-averse stochastic optimization: probabilistically-constrained models and algorithms for black-box distributions. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1627-1646, 2011. 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