An LP-Rounding Based Algorithm for Soft Capacitated Facility Location Problem with Submodular Penalties
摘要
The soft capacitated facility location problem (SCFLP) is a classic combinatorial optimization problem with widespread applications in operations research and computer science. Given a facility set \(\mathcal {F}\) and a client set \(\mathcal {D}\) , each facility i has a capacity \(u_i\) and an open cost \(f_i\) , allowing to open multiple times, and each client j has a demand \(d_j\) . The SCFLP is to find a facility subset in \(\mathcal {F}\) and connect each client to the facilities opened, such that the total cost including open cost and connection cost is minimized. SCFLP is NP-hard, motivating research into approximation algorithms. This paper considers a variant: the soft capacitated facility location problem with submodular penalties (SCFLPSP), where some clients may remain unserved at a penalty cost. We focus on the integer splittable case, where a client’s demand can be served by multiple facilities in integer amounts. Using LP-rounding, we propose a \((\lambda R+4)\) -approximation algorithm, where \(R=\frac{\max _{i \in \mathcal {F} }f_i}{\min _{i \in \mathcal {F} }f_i},\lambda =\frac{R+\sqrt{R^2+8R}}{2R}\) . Notably, when the open cost is uniform, the approximation ratio is 6.