LP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft Penalties
), Abstract
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.
References
J. Byrka and K. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J. Comput., vol. 39, no. 6, pp. 2212–2231, 2010.
F. A. Chudak and D. B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, SIAM J. Comput., vol. 33, no. 1, pp. 1–25, 2004.
S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, J. Algoritms., vol. 31, no. 1, pp. 228–248, 1999.
M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, Analysis of a local search heuristic for facility location problems, J. Algoritms., vol. 37, no. 1, pp. 146–188, 2000.
F. A. Chudak and D. P. Williamson, Improved approximation algorithms for capacitated facility location problems, Math. Program., vol. 102, no. 2, pp. 207–222, 2005.
J. Zhang, B. Chen, and Y. Ye, A multiexchange local search algorithm for the capacitated facility location problem, Math. Oper. Res., vol. 30, no. 2, pp. 389–403, 2005.
E. Angel, N. K. Thang, and D. Regnault, Improved local search for universal facility location, J. Comb. Optim., vol. 29, no. 1, pp. 237–246, 2015.
G. Xu and J. Xu, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties, Inf. Process. Lett., vol. 94, no. 3, pp. 119–123, 2005.
G. Xu and J. Xu, An improved approximation algorithm for uncapacitated facility location problem with penalties, J. Comb. Optim., vol. 17, no. 4, pp. 424–436, 2009.
Y. Li, D. Du, N. Xiu, and D. Xu, Improved approximation algorithms for the facility location problems with linear/submodular penalties, Algorithmica, vol. 73, no. 2, pp. 460–482, 2015.
Y. Li, D. Du, N. Xiu, and D. Xu, A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties, Theor. Comput. Sci., vol. 476, pp. 109–117, 2013.
Y. Xu, D. Xu, D. Du, and C. Wu, Local search algorithm for universal facility location problem with linear penalties, J. Glob. Optim., vol. 67, nos. 1&2, pp. 367–378, 2017.
Y. Xu, D. Xu, D. Du, and C. Wu, Improved approximation algorithm for universal facility location problem with linear penalties, Theor. Comput. Sci., vol. 774, pp. 143–151, 2019.
W. Lv and C. Wu, An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties, J. Comb. Optim., vol. 41, no. 4, pp. 888–904, 2021.
京公网安备11010802044758号