An LP-Rounding Based Algorithm for Hard Capacitated Uniform Facility Location Problem with Soft Penalties
摘要
The hard capacitated facility location problem (HCFLP) is a classical NP-hard problem in combinatorial optimization, with applications in operations research and computer science. Given a set of facilities \(\mathcal {F}\) and clients \(\mathcal {D}\) , each facility has a capacity and open cost, and each client has splittable demand. The goal is to open a subset of facilities and assign client demands to minimize total cost. This paper studies a variant, the hard capacitated uniform facility location problem with soft penalties (HCUFLPSP), where all facilities have uniform opening cost and client demands may be partially rejected at a penalty. We propose a 5-approximation algorithm via LP-rounding, improving upon the 5.5122 ratio of Miao et al. [14].