.png){kind=icon}
返回
LP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft Penalties
.png){kind=icon}
OA
AI
DOI：10.26599/TST.2024.9010040.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Capacitated facility location problem (CFLP) is a classical combinatorial optimization problem that has various applications in operations research, theoretical computer science, and management science. In the CFLP, we have a potential facilities set and a clients set. Each facility has a certain capacity and an open cost, and each client has a spliitable demand that need to be met. The goal is to open some facilities and assign all clients to these open facilities so that the total cost is as low as possible. The CFLP is NP-hard (non-deterministic polynomial-hard), and a large amount of work has been devoted to designing approximation algorithms for CFLP and its variants. Following this vein, we introduce a new variant of CFLP called capacitated uniform facility location problem with soft penalties (CUFLPSP), in which the demand of each client can be partially rejected by paying penalty costs. As a result, we present a linear programming-rounding (LP-rounding) based 5.5122-approximation algorithm for the CUFLPSP.
Keyword:
capacitated facility location problem
approximation algorithm
soft penalties
linear program
capacitated facility location problem
approximation algorithm
soft penalties
linear program
期刊
T
IF:
3.5
论文数:
987
被引数:
2.5K
机构
引用论文
Conserved motifs in nuclear genes encoding predicted mitochondrial proteins in Trypanosoma cruzi.png)
PLOS ONE
OAAI
PLOS ONEIF0
OAAI分享收藏
查看更多内容