A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median

Abstract

In this article, we consider the fault-tolerant k-median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of the classical k-median problem, each client j needs to be assigned to at least r_j ⩾ 1 distinct open facilities. The service cost of j is the sum of its distances to the r_j facilities, and the k-median constraint restricts the number of open facilities to at most k. Previously, a constant factor was known only for the special case when all r_js are the same, and alogarithmic approximation ratio was known for the general case. In addition, we present the first polynomial time algorithm for the fault-tolerant k-median problem on a path or an HST by showing that the corresponding LP always has an integral optimal solution.

We also consider the fault-tolerant facility location problem, in which the service cost of j can be a weighted sum of its distance to the r_j facilities. We give a simple constant factor approximation algorithm, generalizing several previous results that work only for nonincreasing weight vectors.

References

1. K. Aardal, F. A. Chudak, and D. B. Shmoys. 1999. A 3-approximation algorithm for the k-level uncapacitated facility location problem. Information Processing Letters 72, 5--6, 161--167.
2. B. M. Anthony, V. Goyal, A. Gupta, and V. Nagarajan. 2008. A plant location guide for the unsure. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1164--1173.
3. A. Archer, R. Rajagopalan, and D. B. Shmoys. 2003. Lagrangian relaxation for the k-median problem: New insights and continuity properties. In Proceedings of the 11th Annual European Symposium on Algorithms. Springer, 31--42.
4. V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. 2001. Local search heuristic for k-median and facility location problems. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, 21--29.
5. N. Bansal, A. Gupta, and R. Krishnaswamy. 2010. A constant factor approximation algorithm for generalized min-sum set cover. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1539--1545.
6. Y. Bartal. 1998. On approximating arbitrary metrices by tree metrics. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, 161--168.
7. J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan, and K. Trinh. 2015. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 737--756.
8. J. Byrka, A. Srinivasan, and C. Swamy. 2010. Fault-tolerant facility location: A randomized dependent LP-rounding algorithm. Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization. 244--257.
9. R. D. Carr, L. K. Fleischer, V. J. Leung, and C. A. Phillips. 2000. Strengthening integrality gaps for capacitated network design and covering problems. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 106--115.
10. M. Charikar, C. Chekuri, A. Goel, and S. Guha. 1998. Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k-median. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, 114--123.
11. M. Charikar and S. Guha. 2005. Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34, 4 (2005), 803--824.
12. M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys. 2002. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences 65, 1, 129--149.
13. M. Charkar and S. Li. 2012. A dependent LP-rounding approach for the k-median problem. The 39th International Colloquium on Automata, Languages and Programming.
14. S. Chaudhuri, N. Garg, and R. Ravi. 1998. The p-neighbor k-center problem. Information Processing Letters 65, 3, 131--134.
15. F. A. Chudak. 1998. Improved approximation algorithms for uncapacitated facility location. In Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization. Springer, 180--194.
16. F. A. Chudak and D. B. Shmoys. 2004. Improved approximation algorithms for the uncapacitated facility location problem. SIAM Journal on Computing 33, 1, 1--25.
17. J. Chuzhoy and Y. Rabani. 2005. Approximating k-median with non-uniform capacities. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 952--958.
18. H. Ding and J. Xu. 2015. A unified framework for clustering constrained data without locality property. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1471--1490.
19. J. Fakcharoenphol, S. Rao, and K. Talwar. 2003. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. ACM, 448--455.
20. Naveen Garg, Telikepalli Kavitha, Amit Kumar, Kurt Mehlhorn, and Julián Mestre. 2010. Assigning papers to referees. Algorithmica 58, 1, 119--136.
21. S. Guha and S. Khuller. 1998. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 649--657.
22. S. Guha, A. Meyerson, and K. Munagala. 2003. A constant factor approximation algorithm for the fault-tolerant facility location problem. Journal of Algorithms 48, 2, 429--440.
23. M. T. Hajiaghayi, R. Khandekar, and G. Kortsarz. 2010. Budgeted red-blue median and its generalizations. Proceedings of the 18th Annual European Symposium on Algorithms. 314--325.
24. K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani. 2003. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Journal of the ACM 50, 6, 795--824.
25. K. Jain and V. V. Vazirani. 1999. Primal-dual approximation algorithms for metric facility location and k-median problems. In Proceedings of 40th Annual Symposium on Foundations of Computer Science. IEEE, 2--13.
26. K. Jain and V. V. Vazirani. 2001. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM 48, 2, 274--296.
27. K. Jain and V. V. Vazirani. 2003. An approximation algorithm for the fault tolerant metric facility location problem. Algorithmica 38, 3, 433--439.
28. S. Khuller, R. Pless, and Y. Sussmann. 2000. Fault tolerant k-center problems. Theoretical Computer Science 242, 1--2, 237--245.
29. A. Kolen and A. Tamir. 1990. Covering problems. Discrete Location Theory 1995, 263--304.
30. R. Krishnaswamy, A. Kumar, V. Nagarajan, Y. Sabharwal, and B. Saha. 2011. The matroid median problem. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1117--1130.
31. A. Kumar. 2012. Constant factor approximation algorithm for the knapsack median problem. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 824--832.
32. R. Levi, D. Shmoys, and C. Swamy. 2004. LP-based approximation algorithms for capacitated facility location. Proceedings of the 10th Conference on Integer Programming and Combinatorial Optimization. 21--27.
33. J. Li and S. Khuller. 2011. Generalized machine activation problems. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 80--94.
34. S. Li. 2011. A 1.488 approximation algorithm for the uncapacitated facility location problem. In Proceedings of the 38th International Conference on Automata, Languages and Programming - Volume Part II. Springer, 77--88.
35. Shi Li and Ola Svensson. 2013. Approximating k-median via pseudo-approximation. In Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing (STOC’13). 901--910.
36. J. H. Lin and J. S. Vitter. 1992a. Approximation algorithms for geometric median problems. Information Processing Letters 44, 5, 245--249.
37. J. H. Lin and J. S. Vitter. 1992b. e-approximations with minimum packing constraint violation (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing. ACM, 771--782.
38. M. Mahdian and M. Pál. 2003. Universal facility location. Proceedings of the 11th Annual European Symposium on Algorithms. 409--421.
39. M. Pal, T. Tardos, and T. Wexler. 2001. Facility location with nonuniform hard capacities. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 329--338.
40. B. Rybicki and J. Byrka. 2014. Improved approximation algorithm for fault-tolerant facility placement. In Approximation and Online Algorithms. Springer, 59--70.
41. A. Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer.
42. D. B. Shmoys, É. Tardos, and K. Aardal. 1997. Approximation algorithms for facility location problems (extended abstract). In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM, 265--274.
43. Z. Svitkina. 2010. Lower-bounded facility location. ACM Transactions on Algorithms 6, 4, 69.
44. C. Swamy and D. B. Shmoys. 2008. Fault-tolerant facility location. ACM Transactions on Algorithms 4, 4, 1--27.
45. A. Tamir. 1996. An o (pn²) algorithm for the p-median and related problems on tree graphs. Operations Research Letters 19, 59--64.
46. L. Yan and M. Chrobak. 2013. LP-rounding algorithms for the fault-tolerant facility placement problem. In 8th International Conference on Algorithms and Complexity. Springer, 370--381.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis