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.

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

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

  • Hanyin Xiao,
  • Jiaming Zhang,
  • Zhikang Zhang,
  • Weidong Li

摘要

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.