Abstract
Given a set X of n points in a metric space and a radius R, we consider the combining version of k-center and k-median which is with the same objective as k-median, but with the constraint that any x in X is assigned to a center within the range R. In this paper, we propose a bicriteria approximation algorithm achieving a bicriteria approximation ratio of \((3+\varepsilon , 7)\), by incorporating local search with the technology of finding key balls with consequent center exchanges therein. Compared to the state-of-the-art approximation ratio of (8, 4) that is based on an LP formulation for k-median, we improve the ratio of the total distance from 8 to \(3+\varepsilon \) at the price of compromising the ratio of radius from 4 to 7.
Supported by the National Science Foundation of China (Nos. 12271098 and 61772005).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alamdari, S., Shmoys, D.: A bicriteria approximation algorithm for the k-center and k-median problems. In: Solis-Oba, R., Fleischer, R. (eds.) WAOA 2017. LNCS, vol. 10787, pp. 66–75. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89441-6_6
Aouad, A., Segev, D.: The ordered k-median problem: surrogate models and approximation algorithms. Math. Program. 177(1–2), 55–83 (2019)
Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: Proceedings of The Thirty-third Annual ACM Symposium on Theory of Computing, pp. 21–29 (2001)
Byrka, J., Pensyl, T., Rybicki, B, et al.: An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms (TALG) 13(2), 1–31 (2017)
Byrka, J., Sornat, K., Spoerhase, J.: Constant-factor approximation for ordered k-median. In: Proceedings of The 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 620–631 (2018)
Chakrabarty, D., Swamy, C.: Interpolating between k-median and k-center: approximation algorithms for ordered k-median. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (2018)
Chan, T.-H.H., Dinitz, M., Gupta, A.: Spanners with slack. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 196–207. Springer, Heidelberg (2006). https://doi.org/10.1007/11841036_20
Charikar, M., Makarychev, K., Makarychev, Y.: Local global tradeoffs in metric embeddings. SIAM J. Comput. 39(6), 2487–2512 (2010)
Cohen-Addad, V., Gupta, A., Hu, L., Oh, H., Saulpic, D.: An improved local search algorithm for k-median. In: Proceedings of The 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1556–1612 (2022)
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 (JACM) 50(6), 795–824 (2003)
Jung, C., Kannan, S., Lutz, N.: A center in your neighborhood: fairness in facility location. arXiv e-prints, pp. arXiv–1908 (2019)
Kamiyama, N.: The distance-constrained matroid median problem. Algorithmica 82(7), 2087–2106 (2020)
Khoury, B., Pardalos, P.M.: A heuristic for the Steiner problem in graphs. Comput. Optim. Appl. 6, 5–14 (1996)
Li, S., Svensson, O.: Approximating k-median via pseudo-approximation. SIAM J. Comput. 45(2), 530–547 (2016)
Mahabadi, S., Vakilian, A.: Individual fairness for k-clustering. In: International Conference on Machine Learning, pp. 6586–6596 (2020)
Negahbani, M., Chakrabarty, D.: Better algorithms for individually fair \( k \)-clustering. Adv. Neural. Inf. Process. Syst. 34, 13340–13351 (2021)
Nickel, S., Puerto, J.: Location Theory: A Unified Approach. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-27640-8
Swamy, C.: Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Trans. Algorithms (TALG) 12(4), 1–22 (2016)
Vakilian, A., Yalciner, M.: Improved approximation algorithms for individually fair clustering. In: International Conference on Artificial Intelligence and Statistics, pp. 8758–8779 (2022)
Acknowledgments
This work is supported by the Taishan Scholars Young Expert Project of Shandong Province (No. tsqn202211215) and the National Science Foundation of China (Nos. 12271098 and 61772005).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Chi, G., Guo, L. (2024). A Local Search Algorithm for Radius-Constrained k-Median. In: Chen, X., Li, B. (eds) Theory and Applications of Models of Computation. TAMC 2024. Lecture Notes in Computer Science, vol 14637. Springer, Singapore. https://doi.org/10.1007/978-981-97-2340-9_15
Download citation
DOI: https://doi.org/10.1007/978-981-97-2340-9_15
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-2339-3
Online ISBN: 978-981-97-2340-9
eBook Packages: Computer ScienceComputer Science (R0)