{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T14:15:14Z","timestamp":1764339314328,"version":"3.46.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"Research Council of Norway via the project BWCA","award":["314528"],"award-info":[{"award-number":["314528"]}]},{"name":"IIT Jodhpur via the Research Initiation","award":["I\/RIG\/TNI\/20240072"],"award-info":[{"award-number":["I\/RIG\/TNI\/20240072"]}]},{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["819416"],"award-info":[{"award-number":["819416"]}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]},{"name":"European Research Council","award":["101039913 (PARAPATH)"],"award-info":[{"award-number":["101039913 (PARAPATH)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>\n                    We propose a novel clustering model encompassing two well-known clustering models:\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -center clustering and\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -median clustering. In the\n                    <jats:sc>\n                      Hybrid\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      -Clustering\n                    <\/jats:sc>\n                    problem, given a set\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    of points in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {R}^d\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , an integer\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    , and a non-negative real\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    , our objective is to position\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    closed balls of radius\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    to minimize the sum of distances from points not covered by the balls to their closest balls. Equivalently, we seek an optimal\n                    <jats:italic toggle=\"yes\">L<\/jats:italic>\n                    <jats:sub>1<\/jats:sub>\n                    -fitting of a union of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    balls of radius\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    to a set of points in the Euclidean space. When\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    =0, this corresponds to\n                    <jats:sc>\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      -median\n                    <\/jats:sc>\n                    ; when the minimum sum is zero, indicating complete coverage of all points, it is\n                    <jats:sc>\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      -center\n                    <\/jats:sc>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    Our primary result is a bicriteria approximation algorithm that, for a given \u025b &gt; 0, produces a hybrid\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -clustering with balls of radius (1+&gt;)\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    . This algorithm achieves a cost at most 1+&gt; of the optimum, and it operates in time\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{(kd\/\\varepsilon)^{\\mathcal {O}(1)}} \\cdot n^{\\mathcal {O}(1)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . Notably, considering the established lower bounds on\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -center and\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -median, our bicriteria approximation stands as the best possible result for\n                    <jats:sc>\n                      Hybrid\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      -Clustering\n                    <\/jats:sc>\n                    .\n                    <jats:xref ref-type=\"fn\">\n                      <jats:sup>1<\/jats:sup>\n                    <\/jats:xref>\n                  <\/jats:p>","DOI":"10.1145\/3744252","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T07:19:39Z","timestamp":1749453579000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Hybrid k-Clustering: Blending k-Median and k-Center"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor","family":"Fomin","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen","place":["Bergen, Norway"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr","family":"Golovach","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen","place":["Bergen, Norway"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0184-5932","authenticated-orcid":false,"given":"Tanmay","family":"Inamdar","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Jodhpur","place":["Jodhpur, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences","place":["Chennai, India"]},{"name":"Department of Informatics, University of Bergen","place":["Chennai, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3636-5322","authenticated-orcid":false,"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev","place":["Beer-Sheva, Israel"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,28]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00085"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00454-007-9013-2"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-001-0110-Y"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509947"},{"key":"e_1_3_2_6_2","series-title":"Proceedings of Machine Learning Research","first-page":"3151","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","volume":"238","author":"Bateni MohammadHossein","year":"2024","unstructured":"MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, and Silvio Lattanzi. 2024. A scalable algorithm for individually fair k-means clustering. In Proceedings of the International Conference on Artificial Intelligence and Statistics. Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (Eds.), Proceedings of Machine Learning Research, Vol. 238, PMLR, 3151\u20133159. Retrieved from https:\/\/proceedings.mlr.press\/v238\/bateni24a.html"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.101"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188930"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2018.29"},{"key":"e_1_3_2_10_2","first-page":"642","volume-title":"Proceedings of the 12th Annual Symposium on Discrete Algorithms (SODA)","author":"Charikar Moses","year":"2001","unstructured":"Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. 2001. Algorithms for facility location problems with outliers. In Proceedings of the 12th Annual Symposium on Discrete Algorithms (SODA). ACM\/SIAM, 642\u2013651. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=365411.365555"},{"key":"e_1_3_2_11_2","unstructured":"Moses Charikar and Erik Waingarten. 2022. The Johnson-Lindenstrauss lemma for clustering and subspace approximation: From coresets to dimension reduction. arXiv:2205.00371. Retrieved from https:\/\/arxiv.org\/abs\/2205.00371"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.30"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M112717X"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519946"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS54959.2023.00090"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2019.40"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90003-5"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2024.4"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127181"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2025.35"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.002"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","unstructured":"Moses Charikar and Erik Waingarten. 2025. The johnson-lindenstrauss lemma for clustering and subspace approximation: From coresets to dimension reduction. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms SODA 2025 New Orleans LA USA January 12-15 2025 SIAM 3172\u20133209. DOI:10.1137\/1.9781611978322.102","DOI":"10.1137\/1.9781611978322.102"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.COMGEO.2006.02.003"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-004-1123-0"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427963"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.8"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-013-9833-9"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_111"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667054"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_41"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00190-A"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00253-5"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-007-9067-9"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T14:10:23Z","timestamp":1764339023000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,28]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3744252"],"URL":"https:\/\/doi.org\/10.1145\/3744252","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,11,28]]},"assertion":[{"value":"2024-09-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}