{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T11:54:29Z","timestamp":1774007669583,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,10,31]],"date-time":"2021-10-31T00:00:00Z","timestamp":1635638400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation GA\u010cR","doi-asserted-by":"crossref","award":["19-27871X"],"award-info":[{"award-number":["19-27871X"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Center for Foundations of Modern Computer Science","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-19-CE48-0016 and ANR-18-CE40-0004-01"],"award-info":[{"award-number":["ANR-19-CE48-0016 and ANR-18-CE40-0004-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            We consider the classic Facility Location,\n            <jats:italic>k<\/jats:italic>\n            -Median, and\n            <jats:italic>k<\/jats:italic>\n            -Means problems in metric spaces of doubling dimension\n            <jats:italic>d<\/jats:italic>\n            . We give nearly linear-time approximation schemes for each problem. The complexity of our algorithms is\n            <jats:italic>\n              \u00d5(2\n              <jats:sup>(1\/\u03b5)<\/jats:sup>\n              <jats:sup>O(d2)<\/jats:sup>\n              n)\n            <\/jats:italic>\n            , making a significant improvement over the state-of-the-art algorithms that run in time\n            <jats:italic>\n              n\n              <jats:sup>(d\/\u03b5)<\/jats:sup>\n              <jats:sup>O(d)<\/jats:sup>\n            <\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting\n            <jats:italic>k<\/jats:italic>\n            -Median and\n            <jats:italic>k<\/jats:italic>\n            -Means and efficient bicriteria approximation schemes for\n            <jats:italic>k<\/jats:italic>\n            -Median with outliers,\n            <jats:italic>k<\/jats:italic>\n            -Means with outliers and\n            <jats:italic>k<\/jats:italic>\n            -Center.\n          <\/jats:p>","DOI":"10.1145\/3477541","type":"journal-article","created":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T00:27:31Z","timestamp":1635726451000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Near-linear Time Approximation Schemes for Clustering in Doubling Metrics"],"prefix":"10.1145","volume":"68","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, Paris, France and Google Research, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-5332","authenticated-orcid":false,"given":"Andreas Emil","family":"Feldmann","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czechia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4208-8541","authenticated-orcid":false,"given":"David","family":"Saulpic","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2021,10,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.15"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796342"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276718"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 31st International Symposium on Computational Geometry (SoCG\u201915)","author":"Awasthi Pranjal","year":"2015","unstructured":"Pranjal Awasthi , Moses Charikar , Ravishankar Krishnaswamy , and Ali Kemal Sinop . 2015 . The hardness of approximation of euclidean k-means . In Proceedings of the 31st International Symposium on Computational Geometry (SoCG\u201915) . 754\u2013767. Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. 2015. The hardness of approximation of euclidean k-means. In Proceedings of the 31st International Symposium on Computational Geometry (SoCG\u201915). 754\u2013767."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.80"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133102"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897549"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722179"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Hubert Chan T. H.","unstructured":"T. H. Hubert Chan , Shuguang Hu , and Shaofeng H . -C. Jiang. 2016. A PTAS for the steiner forest problem in doubling metrics . In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916) . IEEE, 810\u2013819. T. H. Hubert Chan, Shuguang Hu, and Shaofeng H.-C. Jiang. 2016. A PTAS for the steiner forest problem in doubling metrics. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916). IEEE, 810\u2013819."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365555"},{"key":"e_1_2_1_12_1","unstructured":"Vincent Cohen-Addad. 2018. Approximation schemes for capacitated clustering in doubling metrics. arxiv:1812.07721. Retrieved from http:\/\/arxiv.org\/abs\/1812.07721.  Vincent Cohen-Addad. 2018. Approximation schemes for capacitated clustering in doubling metrics. arxiv:1812.07721. Retrieved from http:\/\/arxiv.org\/abs\/1812.07721."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175298"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.46"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS","volume":"33","author":"Cohen-Addad Vincent","year":"2020","unstructured":"Vincent Cohen-Addad , Silvio Lattanzi , Ashkan Norouzi-Fard , Christian Sohler , and Ola Svensson . 2020 . Fast and accurate $k$-means++ via rejection sampling . In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS 2020), Advances in Neural Information Processing Systems , Vol. 33 , Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svensson. 2020. Fast and accurate $k$-means++ via rejection sampling. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS 2020), Advances in Neural Information Processing Systems, Vol. 33, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.14"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2021326"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62255"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3301446"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Friggstad Zachary","unstructured":"Zachary Friggstad , Mohsen Rezapour , and Mohammad R. Salavatipour . 2016. Local search yields a PTAS for k-means in doubling metrics . In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916) . IEEE, 365\u2013374. Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. 2016. Local search yields a PTAS for k-means in doubling metrics. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916). IEEE, 365\u2013374."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.52"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946308"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_2_1_25_1","volume-title":"InProceedings of the Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Huang Lingxiao","unstructured":"Lingxiao Huang , Shaofeng H-C Jiang , Jian Li , and Xuan Wu . -coresets for clustering (with outliers) in doubling metrics . InProceedings of the Symposium on Foundations of Computer Science (FOCS\u201918) . Lingxiao Huang, Shaofeng H-C Jiang, Jian Li, and Xuan Wu. -coresets for clustering (with outliers) in doubling metrics. InProceedings of the Symposium on Foundations of Computer Science (FOCS\u201918)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702404055"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188882"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.01.007"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873323.1873349"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.034"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_2_1_33_1","volume-title":"The computational complexity of the m-center problems on the plane. IEICE Trans. (1976-1990) 64, 2","author":"Masuyama Shigeru","year":"1981","unstructured":"Shigeru Masuyama , Toshihide Ibaraki , and Toshiharu Hasegawa . 1981. The computational complexity of the m-center problems on the plane. IEICE Trans. (1976-1990) 64, 2 ( 1981 ), 57\u201364. Shigeru Masuyama, Toshihide Ibaraki, and Toshiharu Hasegawa. 1981. The computational complexity of the m-center problems on the plane. IEICE Trans. (1976-1990) 64, 2 (1981), 57\u201364."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010019"},{"key":"e_1_2_1_35_1","unstructured":"Nimrod Megiddo and Kenneth J. Supowit. On the complexity of some common geometric location problems. (unpublished)  Nimrod Megiddo and Kenneth J. Supowit. On the complexity of some common geometric location problems. (unpublished)"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701388884"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477541","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477541","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:37Z","timestamp":1750183837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477541"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,31]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3477541"],"URL":"https:\/\/doi.org\/10.1145\/3477541","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,31]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}