Approximating Per-Scenario Bound for the Two-Stage Stochastic Facility Location Problem
摘要
The two-stage stochastic facility location problem (2-SFLP) involves selecting initial facility locations under uncertainty, given known probabilities for each demand scenario. After the actual demand scenario is realized, additional facilities in the second stage, which incur higher costs, may be added to reduce the overall expected cost, including both opening and connection expenses. We present an improved per-scenario bound of 2.322 for 2-SFLP using the LP-rounding algorithm from prior work. By introducing the integrated distance estimation technique, we offer a more refined analysis. This technique, which involves a detailed estimation through a non-negative linear combination of the maximum and average distances within the neighborhood of an arbitrary client-scenario pair, has potential applications for the analysis of other facility location problems.