Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.23
URN: urn:nbn:de:0030-drops-147163
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14716/
Brubach, Brian ; Grammel, Nathaniel ; Harris, David G. ; Srinivasan, Aravind ; Tsepenekas, Leonidas ; Vullikanti, Anil
Approximating Two-Stage Stochastic Supplier Problems
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{brubach_et_al:LIPIcs.APPROX/RANDOM.2021.23,
author = {Brubach, Brian and Grammel, Nathaniel and Harris, David G. and Srinivasan, Aravind and Tsepenekas, Leonidas and Vullikanti, Anil},
title = {{Approximating Two-Stage Stochastic Supplier Problems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {23:1--23:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-207-5},
ISSN = {1868-8969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14716},
URN = {urn:nbn:de:0030-drops-147163},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.23},
annote = {Keywords: Approximation Algorithms, Stochastic Optimization, Two-Stage Recourse Model, Clustering Problems, Knapsack Supplier}
}
| Keywords: | Approximation Algorithms, Stochastic Optimization, Two-Stage Recourse Model, Clustering Problems, Knapsack Supplier | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 15.09.2021 |
