LP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft Penalties  

作　　者：Runjie Miao Chenchen Wu Jinjiang Yuan 

机构地区：[1]School of Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,China [2]Institute of Operations Research and Systems Engineering,Tianjin University of Technology,Tianjin 300384,China

出　　处：《Tsinghua Science and Technology》2025年第1期279-289,共11页清华大学学报自然科学版(英文版)

基　　金：supported by the National Natural Science Foundation of China(Nos.11971349,12071442,12371320,and 12371318).

摘　　要：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.

关 键 词：capacitated facility location problem approximation algorithm soft penalties linear program 

分 类 号：F22[经济管理—国民经济]