2026-08-17T16:13:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14716 2024-03-06T10:54:43Z ddc:004 open_access

Approximating Two-Stage Stochastic Supplier Problems Brubach, Brian Grammel, Nathaniel Harris, David G. Srinivasan, Aravind Tsepenekas, Leonidas Vullikanti, Anil Approximation Algorithms Stochastic Optimization Two-Stage Recourse Model Clustering Problems Knapsack Supplier 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Brian Brubach and Nathaniel Grammel and David G. Harris and Aravind Srinivasan and Leonidas Tsepenekas and Anil Vullikanti 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.23 urn:nbn:de:0030-drops-147163 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.23 eng https://creativecommons.org/licenses/by/4.0/legalcode