Approximating Two-Stage Stochastic Supplier Problems
Preprint
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 handle 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, where all scenarios are explicitly provided; second, we employ a novel scenario-discarding variant of the standard Sample Average Approximation (SAA) method, which crucially exploits properties of the restricted-case algorithms. We note that the scenario-discarding modification to the SAA method is necessary in order to optimize over the radius.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Generalized Center Problems with OutliersACM Transactions on Algorithms, 2019
- Iterative Methods in Combinatorial Optimization2011
- Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization ProblemsSIAM Journal on Computing, 2011
- An approximation scheme for stochastic linear programming and its application to stochastic integer programsJournal of the ACM, 2006
- Approximation algorithms for 2-stage stochastic optimization problemsACM SIGACT News, 2006
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a GraphSIAM Journal on Computing, 2006
- Sampling-based Approximation Algorithms for Multi-stage Stochastic2005
- The Sample Average Approximation Method for Stochastic Discrete OptimizationSIAM Journal on Optimization, 2002
- A unified approach to approximation algorithms for bottleneck problemsJournal of the ACM, 1986
- On Minimizing a Convex Function Subject to Linear InequalitiesJournal of the Royal Statistical Society Series B: Statistical Methodology, 1955