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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Approximating Per-Scenario Bound for the Two-Stage Stochastic Facility Location Problem

  • Mengzhen Li,
  • Chenchen Wu,
  • Dachuan Xu,
  • Yicheng Xu

摘要

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.