Scholarlink

The two-stage stochastic facility location problem (SFL) has been extensively studied in the literature. However, as a crucial and worthwhile direction of SFL, the capacity variant of the SFL remains relatively underexplored. In this work, we give the first constant 3.7052-approximation ratio for the soft capacitated two-stage stochastic facility location problem (SCSFL). Initially, we present a 6-approximation algorithm for the SCSFL by utilizing the 3-approximation algorithm for the SFL. Subsequently, we enhance this algorithm through greedy improvement and cost scaling, achieving a significant reduction in the approximation ratio to 3.7052.

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

Soft Capacitated Two-Stage Stochastic Facility Location Problem

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Yingying Guo,
  • Qiaoliang Li,
  • Li Zhang

摘要

The two-stage stochastic facility location problem (SFL) has been extensively studied in the literature. However, as a crucial and worthwhile direction of SFL, the capacity variant of the SFL remains relatively underexplored. In this work, we give the first constant 3.7052-approximation ratio for the soft capacitated two-stage stochastic facility location problem (SCSFL). Initially, we present a 6-approximation algorithm for the SCSFL by utilizing the 3-approximation algorithm for the SFL. Subsequently, we enhance this algorithm through greedy improvement and cost scaling, achieving a significant reduction in the approximation ratio to 3.7052.