Search for: All records

The main focus of this article 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. In addition to the standard (homogeneous) setting where all clients must be within a distance\(R\)of the nearest facility, we provide results for the more general problem where the radius demands may beinhomogeneous(i.e., different for each client). We also explore a number of variants where additional constraints are imposed on the first-stage decisions, specifically matroid and multi-knapsack constraints, and provide results for these settings. We derive results for the most general distributional setting, where there is only black-box access to the underlying distribution. To accomplish this, we first develop algorithms for thepolynomial scenariossetting; we then employ a novelscenario-discardingvariant of the standardSample Average Approximationmethod, which crucially exploits properties of the restricted-case algorithms. We note that the scenario-discarding modification to the SAA method is necessary to optimize over the radius.