Approximation Algorithms for Radius-Based, Two-Stage Stochastic Clustering Problems with Budget Constraints
share
The main focus of this paper is radius-based clustering problems 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. Further, we show that our problems have natural applications to allocating healthcare testing centers. The eventual goal is to provide results for supplier-like problems in the most general distributional setting, where there is only black-box access to the underlying distribution. Our framework unfolds in two steps. First, we develop algorithms for a restricted version of each problem, in which all possible scenarios are explicitly provided; second, we exploit structural properties of these algorithms and generalize them to the black-box setting. These key properties are: (1) the algorithms produce “simple” exponential families of black-box strategies, and (2) there exist efficient ways to extend their output to the black-box case, which also preserve the approximation ratio exactly. We note that prior generalization approaches, i.e., variants of the Sample Average Approximation method, can be used for the problems we consider, however they would yield worse approximation guarantees.
READ FULL TEXT