{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:54:23Z","timestamp":1781078063816,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520011","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1621-1628","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Improved approximations for Euclidean\n            <i>k<\/i>\n            -means and\n            <i>k<\/i>\n            -median, via nested quasi-independent sets"],"prefix":"10.1145","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google Research, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hossein","family":"Esfandiari","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shyam","family":"Narayanan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","article-title":"Better guarantees for k-means and Euclidean k-median by primal-dual algorithms","volume":"49","author":"Ahmadian Sara","year":"2019","unstructured":"Sara Ahmadian , Ashkan Norouzi-Fard , Ola Svensson , and Justin Ward . 2019 . Better guarantees for k-means and Euclidean k-median by primal-dual algorithms . SIAM J. Comput. 49 , 4 ( 2019 ), FOCS17-97-FOCS17-156. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. 2019. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. SIAM J. Comput. 49, 4 ( 2019 ), FOCS17-97-FOCS17-156.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007","author":"Arthur David","year":"2007","unstructured":"David Arthur and Sergei Vassilvitskii . 2007 . k-means++: the advantages of careful seeding . In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 , New Orleans, Louisiana, USA , January 7-9, 2007, Nikhil Bansal, Kirk Pruhs, and Cliford Stein (Eds.). SIAM, 1027-1035. http:\/\/dl.acm.org\/citation.cfm?id= 1283383. 1283494 David Arthur and Sergei Vassilvitskii. 2007. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, Nikhil Bansal, Kirk Pruhs, and Cliford Stein (Eds.). SIAM, 1027-1035. http:\/\/dl.acm.org\/citation.cfm?id= 1283383. 1283494"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683921"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SOCG.2015.754"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2016.14"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316318"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2981561"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398594"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_17"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.29"},{"key":"e_1_3_2_1_14_1","unstructured":"Vincent Cohen-Addad Hossein Esfandiari Vahab Mirrokni and Shyam Narayanan. 2022. Improved Approximations for Euclidean k-means and k-median via Nested Quasi-Independent Sets. CoRR abs\/2204.04828 ( 2022 ).   Vincent Cohen-Addad Hossein Esfandiari Vahab Mirrokni and Shyam Narayanan. 2022. Improved Approximations for Euclidean k-means and k-median via Nested Quasi-Independent Sets. CoRR abs\/2204.04828 ( 2022 )."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.65"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00040"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM.","author":"Cohen-Addad Vincent","unstructured":"Vincent Cohen-Addad , Euiwoong Lee , and Karthik C. S . 2022. Johnson Coverage Hypothesis: Inapproximability of-means and-median in \u2113 metrics . In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM. Vincent Cohen-Addad, Euiwoong Lee, and Karthik C. S. 2022. Johnson Coverage Hypothesis: Inapproximability of-means and-median in \u2113 metrics. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SOCG.2015.329"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.156"},{"key":"e_1_3_2_1_21_1","volume-title":"The hardness of k-means clustering. Department of Computer Science and Engineering","author":"Dasgupta Sanjoy","unstructured":"Sanjoy Dasgupta . 2008. The hardness of k-means clustering. Department of Computer Science and Engineering , University of California .... Sanjoy Dasgupta. 2008. The hardness of k-means clustering. Department of Computer Science and Engineering, University of California...."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993712"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2022.106251"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644198"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"S Louis Hakimi. 1964. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations research 12 3 ( 1964 ) 450-459.   S Louis Hakimi. 1964. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations research 12 3 ( 1964 ) 450-459.","DOI":"10.1287\/opre.12.3.450"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1100"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667054"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.11.009"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.01.007"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938645"},{"key":"e_1_3_2_1_35_1","volume-title":"Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd","author":"Lloyd SP","year":"1957","unstructured":"SP Lloyd . 1957. Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd , SP : Least squares quantization in PCM. IEEE Trans. Inform. Theor .( 1957 \/ 1982 ) 18 ( 1957 ). SP Lloyd. 1957. Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, SP: Least squares quantization in PCM. IEEE Trans. Inform. Theor.( 1957 \/ 1982 ) 18 ( 1957 )."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.14"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010019"},{"key":"e_1_3_2_1_39_1","series-title":"SIAM journal on computing 13, 1 ( 1984 ), 182-196","volume-title":"On the complexity of some common geometric location problems","author":"Megiddo Nimrod","unstructured":"Nimrod Megiddo and Kenneth J Supowit . 1984. On the complexity of some common geometric location problems . SIAM journal on computing 13, 1 ( 1984 ), 182-196 . Nimrod Megiddo and Kenneth J Supowit. 1984. On the complexity of some common geometric location problems. SIAM journal on computing 13, 1 ( 1984 ), 182-196."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00041"},{"key":"e_1_3_2_1_41_1","first-page":"801","volume-title":"Cl. III 4 ( 1957 )","author":"Steinhaus Hugo","unstructured":"Hugo Steinhaus . 1957. Sur la division des corps mat\u00e9riels en parties. Bull. Acad. Pol. Sci ., Cl. III 4 ( 1957 ) , 801 - 804 . Hugo Steinhaus. 1957. Sur la division des corps mat\u00e9riels en parties. Bull. Acad. Pol. Sci., Cl. III 4 ( 1957 ), 801-804."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520011","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520011","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520011"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":41,"alternative-id":["10.1145\/3519935.3520011","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520011","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}