{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T04:21:40Z","timestamp":1744258900377,"version":"3.40.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T00:00:00Z","timestamp":1738195200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T00:00:00Z","timestamp":1738195200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12271098","12271098","12271098"],"award-info":[{"award-number":["12271098","12271098","12271098"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s00224-024-10211-w","type":"journal-article","created":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T11:10:59Z","timestamp":1738235459000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Local Search Algorithm for the Radius-Constrained k-Median Problem"],"prefix":"10.1007","volume":"69","author":[{"given":"Gaojie","family":"Chi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2891-4253","authenticated-orcid":false,"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6548-390X","authenticated-orcid":false,"given":"Chaoqi","family":"Jia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,30]]},"reference":[{"key":"10211_CR1","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J Gramm","year":"2005","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: exact algorithms for clique generation. Theory Comput Syst 38, 373\u2013392 (2005)","journal-title":"Theory Comput Syst"},{"key":"10211_CR2","doi-asserted-by":"crossref","unstructured":"Cormode, G., McGregor, A.: Approximation algorithms for clustering uncertain data. In: Proceedings of the Twenty-seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 191\u2013200 (2008)","DOI":"10.1145\/1376916.1376944"},{"issue":"8","key":"10211_CR3","doi-asserted-by":"publisher","first-page":"3633","DOI":"10.1137\/070698257","volume":"39","author":"G Lin","year":"2010","unstructured":"Lin, G., Nagarajan, C., Rajaraman, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. SIAM J. Comput. 39(8), 3633\u20133669 (2010)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"10211_CR4","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"28","author":"T Kanungo","year":"2004","unstructured":"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(2\u20133), 89\u2013112 (2004)","journal-title":"Comput. Geom."},{"key":"10211_CR5","doi-asserted-by":"crossref","unstructured":"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 (STOC), pp. 21\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"issue":"2","key":"10211_CR6","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the $$k$$-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"key":"10211_CR7","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.artint.2015.05.006","volume":"244","author":"K-C Duong","year":"2017","unstructured":"Duong, K.-C., Vrain, C., et al.: Constrained clustering by constraint programming. Artif. Intell. 244, 70\u201394 (2017)","journal-title":"Artif. Intell."},{"issue":"2","key":"10211_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2983633","volume":"13","author":"S Li","year":"2017","unstructured":"Li, S.: On uniform capacitated $$k$$-median beyond the natural lp relaxation. ACM Transactions on Algorithms (TALG) 13(2), 1\u201318 (2017)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"4","key":"10211_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2728170","volume":"9","author":"F Bonchi","year":"2015","unstructured":"Bonchi, F., Gionis, A., Gullo, F., Tsourakakis, C.E., Ukkonen, A.: Chromatic correlation clustering. ACM Transactions on Knowledge Discovery from Data (TKDD) 9(4), 1\u201324 (2015)","journal-title":"ACM Transactions on Knowledge Discovery from Data (TKDD)"},{"key":"10211_CR10","doi-asserted-by":"crossref","unstructured":"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\u20131612 (2022)","DOI":"10.1137\/1.9781611977073.65"},{"issue":"2","key":"10211_CR11","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1137\/130938645","volume":"45","author":"S Li","year":"2016","unstructured":"Li, S., Svensson, O.: Approximating $$k$$-median via pseudo-approximation. SIAM J. Comput. 45(2), 530\u2013547 (2016)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10211_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2981561","volume":"13","author":"J Byrka","year":"2017","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for $$k$$-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms (TALG) 13(2), 1\u201331 (2017)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"6","key":"10211_CR13","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp. Journal of the ACM (JACM) 50(6), 795\u2013824 (2003)","journal-title":"Journal of the ACM (JACM)"},{"key":"10211_CR14","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"10211_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W-L Hsu","year":"1979","unstructured":"Hsu, W.-L., Nemhauser, G.L.: Easy and hard bottleneck location problems. Discret. Appl. Math. 1(3), 209\u2013215 (1979)","journal-title":"Discret. Appl. Math."},{"key":"10211_CR16","unstructured":"Jung, C., Kannan, S., Lutz, N.: Service in your neighborhood: Fairness in center location. Foundations of Responsible Computing (FORC) (2020)"},{"key":"10211_CR17","unstructured":"Mahabadi, S., Vakilian, A.: Individual fairness for $$k$$-clustering. In: Proceedings of the 37th International Conference on Machine Learning (ICML), pp. 6586\u20136596 (2020)"},{"key":"10211_CR18","first-page":"13340","volume":"34","author":"M Negahbani","year":"2021","unstructured":"Negahbani, M., Chakrabarty, D.: Better algorithms for individually fair $$k$$-clustering. Advances in Neural Information Processing Systems (NeurIPS) 34, 13340\u201313351 (2021)","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"10211_CR19","unstructured":"Vakilian, A., Yalciner, M.: Improved approximation algorithms for individually fair clustering. In: International Conference on Artificial Intelligence and Statistics, PMLR, pp. 8758\u20138779 (2022)"},{"issue":"4","key":"10211_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2963170","volume":"12","author":"C Swamy","year":"2016","unstructured":"Swamy, C.: Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Transactions on Algorithms (TALG) 12(4), 1\u201322 (2016)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"10211_CR21","doi-asserted-by":"crossref","unstructured":"Alamdari, S., Shmoys, D.: A bicriteria approximation algorithm for the $$k$$-center and $$k$$-median problems. In: International Workshop on Approximation and Online Algorithms, Springer, pp. 66\u201375 (2018)","DOI":"10.1007\/978-3-319-89441-6_6"},{"issue":"1\u20132","key":"10211_CR22","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10107-018-1259-3","volume":"177","author":"A Aouad","year":"2019","unstructured":"Aouad, A., Segev, D.: The ordered $$k$$-median problem: surrogate models and approximation algorithms. Math. Program. 177(1\u20132), 55\u201383 (2019)","journal-title":"Math. Program."},{"key":"10211_CR23","doi-asserted-by":"crossref","unstructured":"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\u2013631 (2018)","DOI":"10.1145\/3188745.3188930"},{"key":"10211_CR24","unstructured":"Nickel, S., Albandoz, J.P.: Location theory. Springer Books (2005)"},{"issue":"7","key":"10211_CR25","doi-asserted-by":"publisher","first-page":"2087","DOI":"10.1007\/s00453-020-00688-5","volume":"82","author":"N Kamiyama","year":"2020","unstructured":"Kamiyama, N.: The distance-constrained matroid median problem. Algorithmica 82(7), 2087\u20132106 (2020)","journal-title":"Algorithmica"},{"key":"10211_CR26","doi-asserted-by":"crossref","unstructured":"Chan, T.-H.H., Dinitz, M., Gupta, A.: Spanners with slack. In: European Symposium on Algorithms, pp. 196\u2013207 (2006)","DOI":"10.1007\/11841036_20"},{"issue":"6","key":"10211_CR27","doi-asserted-by":"publisher","first-page":"2487","DOI":"10.1137\/070712080","volume":"39","author":"M Charikar","year":"2010","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Local global tradeoffs in metric embeddings. SIAM J. Comput. 39(6), 2487\u20132512 (2010)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10211-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10211-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10211-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:52:16Z","timestamp":1744217536000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10211-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,30]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10211"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10211-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,1,30]]},"assertion":[{"value":"25 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"11"}}