Approximation algorithm for squared metric facility location problem with nonuniform capacities. (English) Zbl 1422.90047
Summary: Facility location problem is one of the most classical NP-hard problems in combinatorial optimization. In the metric facility location problem (MFLP), we are given a set of facilities, a set of clients and the metric distances between facilities and clients. In this paper, we consider the squared metric facility location problem (SMFLP) with nonuniform capacities, where each facility has a nonuniform capacity to serve a limited amount of client demands, and the distances between facilities and clients are no longer metric but squared metric. C. G. Fernandes et al. [Math. Program. 153, No. 2 (A), 655–685 (2015; Zbl 1369.90143)] analyzed the LP-based algorithms for the MFLP when they are applied to the SMFLP and achieve constant approximation ratios. In this paper, we do the same thing on local search algorithm, one of the most powerful techniques for MFLP with nonuniform capacities. Particularly, we propose the first constant approximation algorithm with approximation ratio \(13 + \epsilon\) for the SMFLP with nonuniform capacities.
MSC:
| 90C27 | Combinatorial optimization |
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Citations:
Zbl 1369.90143References:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms, and Applications (1993) · Zbl 1201.90001 |
| [2] | An, H. C.; Singh, M.; Svensson, O., LP-based algorithms for capacitated facility location, SIAM J. Comput., 46, 272-306 (2017) · Zbl 1359.68298 |
| [3] | Arya, V.; Garg, N.; Khandekar, R.; Meyerson, A.; Munagala, K.; Pandit, V., Local search heuristics for k-median and facility location problems, SIAM J. Comput., 33, 544-562 (2004) · Zbl 1105.68118 |
| [4] | Blum, C.; Puchinger, J.; Raidl, G. R.; Roli, A., Hybrid metaheuristics in combinatorial optimization: A survey, Appl. Soft Comput., 11, 4135-4151 (2011) |
| [5] | Byrka, J.; Aardal, K., An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J. Comput., 39, 2212-2231 (2010) · Zbl 1205.90173 |
| [6] | Chudak, F. A.; Shmoys, D. B., Improved approximation algorithms for the uncapacitated facility location problem, SIAM J. Comput., 33, 1-25 (2003) · Zbl 1044.90056 |
| [7] | Fernandes, C. G.; Meira, L. A.A.; Miyazawa, F. K.; Pedrosa, L. L., A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems, Math. Program., 153, 655-685 (2015) · Zbl 1369.90143 |
| [8] | Ghosh, D., Neighborhood search heuristics for the uncapacitated facility location problem, European J. Oper. Res., 150, 150-162 (2003) · Zbl 1023.90524 |
| [9] | Guha, S.; Khuller, S., Greedy strikes back: improved facility location algorithms, J. Algorithms, 31, 228-248 (1999) · Zbl 0928.68137 |
| [10] | Jain, K.; Mahdian, M.; Markakis, E.; Saberi, A.; Vazirani, V. V., Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM, 50, 795-824 (2003) · Zbl 1325.90060 |
| [11] | Jain, K.; Vazirani, V. V., Approximation algorithms for metric facility location and \(k\)-median problems using the primal – dual schema and Lagrangian relaxation, J. ACM, 48, 274-296 (2001) · Zbl 1138.90417 |
| [12] | Kanungo, T.; Mount, D. M.; Netanyahu, N. S.; Piatko, C. D.; Silverman, R.; Wu, A. Y., A local search approximation algorithm for \(k\)-means clustering, Comput. Geom., 28, 89-112 (2004) · Zbl 1077.68109 |
| [13] | Korupolu, M. R.; Plaxton, C. G.; Rajaraman, R., Analysis of a local search heuristic for facility location problems, J. Algorithms, 37, 146-188 (2000) · Zbl 0962.68044 |
| [14] | Lee, E.; Schmidt, M.; Wright, J., Improved and simplified inapproximability for \(k\)-means, Inform. Process. Lett., 120, 40-43 (2017) · Zbl 1400.68250 |
| [15] | Li, S., A 1.488 approximation algorithm for the uncapacitated facility location problem, Inform. and Comput., 222, 45-58 (2013) · Zbl 1281.68236 |
| [16] | Matoušek, J., On approximate geometric \(k\)-clustering, Discrete Comput. Geom., 24, 61-84 (2000) · Zbl 0959.68126 |
| [17] | M. Pál, E. Tardös, T. Wexler, Facility location with nonuniform hard capacities, in: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001, pp. 329-338.; M. Pál, E. Tardös, T. Wexler, Facility location with nonuniform hard capacities, in: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001, pp. 329-338. |
| [18] | Raidl, G. R.; Puchinger, J., Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization, (Hybrid Metaheuristics (2008), Springer: Springer Berlin, Heidelberg), 31-62 · Zbl 1415.90054 |
| [19] | Resende, M. G.C.; Werneck, R. F., A hybrid multistart heuristic for the uncapacitated facility location problem, European J. Oper. Res., 174, 54-68 (2006) · Zbl 1116.90074 |
| [20] | Zhang, J.; Chen, B.; Ye, Y., A multiexchange local search algorithm for the capacitated facility location problem, Math. Oper. Res., 30, 389-403 (2005) · Zbl 1082.90057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
