An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. (English) Zbl 1177.90257
Summary: We consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP, for short) in which each client can be either assigned to some opened facility or rejected by paying a penalty. Existing approaches for this variant of facility location problem are all based on primal-dual method. In this paper, we present an efficient linear programming (LP) rounding based approach to show that LP rounding techniques are equally capable of solving this variant of facility location problem. Our algorithm uses a two-phase filtering technique to identify those to-be-rejected clients and open facilities for the remaining ones. Our approach achieves an approximation ratio of \(2+2/e\) (\(\approx 2.736\)) which is worse than the best approximation ratio of 2 achieved by the much more sophisticated dual fitting technique, but better than the approximation ratio of 3 achieved by the primal-dual method. Our algorithm is simple, natural, and can be easily integrated into existing LP rounding based algorithms for facility location problem to deal with outliers.
References:
| [1] | V. Arya, N. Garg, A. Meyerson, K. Munagala, V. Pandit, Local search heuristics for \(k\); V. Arya, N. Garg, A. Meyerson, K. Munagala, V. Pandit, Local search heuristics for \(k\) · Zbl 1323.90031 |
| [2] | Chudak, F. A.; Shmoys, D. B., Improved approximation algorithms for uncapacitated facility location, SIAM J. Comput., 33, 1, 1-25 (2003) · Zbl 1044.90056 |
| [3] | M. Charikar, S. Guha, Improved combinatorial algorithms for facility location and \(k\); M. Charikar, S. Guha, Improved combinatorial algorithms for facility location and \(k\) · Zbl 1075.68100 |
| [4] | M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, pp. 642-651; M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, pp. 642-651 · Zbl 1012.90026 |
| [5] | S. Guha, S. Khuller, Greedy strikes back: improved facility location algorithms, in: Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, 1998, pp. 649-657; S. Guha, S. Khuller, Greedy strikes back: improved facility location algorithms, in: Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, 1998, pp. 649-657 · Zbl 0936.68114 |
| [6] | Hochbaum, D., Approximation Algorithms for NP-Hard Problems (1997), PWS Publishing Company: PWS Publishing Company Boston, MA |
| [7] | K. Jain, V. Vazirani, Approximation algorithms for metric facility location and \(k\); K. Jain, V. Vazirani, Approximation algorithms for metric facility location and \(k\) |
| [8] | 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 |
| [9] | Lin, J.-H.; Vitter, J. S., Approximation algorithms for geometric median problems, Inform. Process. Lett., 44, 245-249 (1992) · Zbl 0764.68079 |
| [10] | J.-H. Lin, J.S. Vitter, \(ϵ\); J.-H. Lin, J.S. Vitter, \(ϵ\) |
| [11] | Shmoys, D. B., Approximation algorithms for facility location problem, (Jansen, K.; Khuller, S., Approximation Algorithms for Combinatorial Optimization. Approximation Algorithms for Combinatorial Optimization, Lecture Notes in Comput. Sci., vol. 1913 (2000), Springer: Springer Berlin), 27-33 · Zbl 0976.68538 |
| [12] | D.B. Shmoys, É. Tardos, K. Aardal, Approximation algorithms for facility location problems, in: Proc. 29th ACM Symp. on Theory of Computing, 1997, pp. 265-274; D.B. Shmoys, É. Tardos, K. Aardal, Approximation algorithms for facility location problems, in: Proc. 29th ACM Symp. on Theory of Computing, 1997, pp. 265-274 · Zbl 0962.68008 |
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.
