A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. (English) Zbl 1369.90143
The paper describes a systematic approach for obtaining upper bound-factor revealing linear programs. The authors apply this technique to the metric facility location problem (MFLP) and the squared metric facility location problem (SMFLP). They prove that unless \(P \neq NP\), there is no approximation factor better than \(2.04\). They show that an LP-rounding algorithm for MFLP when applied to SMFLP achieves the best possible ratio of \(2.04\).
Reviewer: Matthias Ehrgott (Lancaster)
MSC:
| 90C27 | Combinatorial optimization |
| 68W25 | Approximation algorithms |
| 90C20 | Quadratic programming |
| 90B80 | Discrete location and assignment |
References:
| [1] | Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean \[k\] k-medians and related problems. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 106-113 (1998) · Zbl 1027.68979 |
| [2] | 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 · doi:10.1137/070708901 |
| [3] | Byrka, J., Ghodsi, M., Srinivasan, A.: LP-Rounding Algorithms for Facility-Location Problems (2010). http://arxiv.org/abs/1007.3611 |
| [4] | Charikar, M., Guha, S., Tardos, É., Shmoys, D.B.: A constant-factor approximation algorithm for the \[k\] k-median problem. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 1-10 (1999) · Zbl 1346.68253 |
| [5] | Chudak, F., Shmoys, D.: Improved approximation algorithms for the capacitated facility location problem. In: Proceedings 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 875-876 (1999) · Zbl 1052.90580 |
| [6] | Chudak, F., Shmoys, D.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1-25 (2004) · Zbl 1044.90056 · doi:10.1137/S0097539703405754 |
| [7] | Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: Proceedings of the 9th Annual ACM-SIAM Sympsoium on Discrete Algorithms, pp. 649-657 (1998) · Zbl 0936.68114 |
| [8] | Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31(1), 228-248 (1999) · Zbl 0928.68137 · doi:10.1006/jagm.1998.0993 |
| [9] | Hochbaum, D.: Heuristics for the fixed cost median problem. Math. Program. 22(2), 148-162 (1982) · Zbl 0473.90029 · doi:10.1007/BF01581035 |
| [10] | Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795-824 (2003) · Zbl 1325.90060 · doi:10.1145/950620.950621 |
| [11] | Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 731-740 (2002) · Zbl 1192.90106 |
| [12] | Jain, K., Vazirani, V.: Approximation algorithms for metric facility location and \[k\] k-Median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274-296 (2001) · Zbl 1138.90417 · doi:10.1145/375827.375845 |
| [13] | Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45-58 (2013) · Zbl 1281.68236 · doi:10.1016/j.ic.2012.01.007 |
| [14] | Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 597-606 (2011) · Zbl 1288.68288 |
| [15] | Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411-432 (2006) · Zbl 1151.90590 · doi:10.1137/S0097539703435716 |
| [16] | Shmoys, D., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265-274 (1997) · Zbl 0962.68008 |
| [17] | Shmoys, D.B., Tardos, É., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265-274. ACM (1997) · Zbl 0962.68008 |
| [18] | Sviridenko, M.; Cook, WJ (ed.); Schulz, AS (ed.), An improved approximation algorithm for the metric uncapacitated facility location problem, No. 2337, 240-257 (2002), Berlin · Zbl 1049.90520 · doi:10.1007/3-540-47867-1_18 |
| [19] | Vygen, J.: Approximation Algorithms for Facility Location Problems (Lecture Notes). Technical Report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn (2005) |
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.
