{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:03Z","timestamp":1781031423049,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2313372"],"award-info":[{"award-number":["CCF-2313372"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2443697"],"award-info":[{"award-number":["CCF-2443697"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2517033"],"award-info":[{"award-number":["CCF-2517033"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2237288"],"award-info":[{"award-number":["CCF-2237288"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["459420781"],"award-info":[{"award-number":["459420781"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["850979"],"award-info":[{"award-number":["850979"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800753","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"330-341","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fine-Grained Complexity of Continuous Euclidean k-Center"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6410-8323","authenticated-orcid":false,"given":"Lotte","family":"Blank","sequence":"first","affiliation":[{"name":"University of Bonn, Bonn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1356-5177","authenticated-orcid":false,"given":"Karl","family":"Bringmann","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2833-0472","authenticated-orcid":false,"given":"Parinya","family":"Chalermsook","sequence":"additional","affiliation":[{"name":"University of Sheffield, Sheffield, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9105-364X","authenticated-orcid":false,"family":"Karthik C. S.","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0440-4912","authenticated-orcid":false,"given":"Benedikt","family":"Kolbe","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8223-9944","authenticated-orcid":false,"given":"Hung","family":"Le","sequence":"additional","affiliation":[{"name":"University of Massachusetts at Amherst, Amherst, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2650-638X","authenticated-orcid":false,"given":"Geert","family":"van Wordragen","sequence":"additional","affiliation":[{"name":"Aalto University, Espoo, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1810974"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220284"},{"key":"e_1_3_2_1_3_1","volume-title":"Agarwal and Cecilia Magdalena Procopiuc","author":"Pankaj","year":"1998","unstructured":"Pankaj K. Agarwal and Cecilia Magdalena Procopiuc. 1998. Exact and Approximation Algorithms for Clustering. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Howard J. Karloff (Ed.). ACM\/SIAM, 658\u2013667. http:\/\/dl.acm.org\/citation.cfm?id=314613.315040"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0110-y"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182774"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/299917.299918"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009387"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 3, 801\u2013802","author":"Badoiu Mihai","year":"2003","unstructured":"Mihai Badoiu and Kenneth L Clarkson. 2003. Smaller core-sets for balls. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 3, 801\u2013802."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509947"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i4.20305"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Lotte Blank Karl Bringmann Parinya Chalermsook Karthik C. S. Benedikt Kolbe Hung Le and Geert van Wordragen. 2026. Fine-Grained Complexity of Continuous Euclidean k-Center. arxiv:2603.28265. https:\/\/doi.org\/10.48550\/arXiv.2603.28265 10.48550\/arXiv.2603.28265","DOI":"10.48550\/arXiv.2603.28265"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400831470"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000811"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00019-X"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.34"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SOCG.2022.28"},{"key":"e_1_3_2_1_17_1","volume-title":"Optimal algorithm for the planar two-center problem. TheoretiCS, 3","author":"Cho Kyungjin","year":"2024","unstructured":"Kyungjin Cho, Eunjin Oh, Haitao Wang, and Jie Xue. 2024. Optimal algorithm for the planar two-center problem. TheoretiCS, 3 (2024)."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.63"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_2_1_20_1","first-page":"741","article-title":"The p-centre problem\u2014heuristic and optimal algorithms","volume":"35","author":"Drezner Zvi","year":"1984","unstructured":"Zvi Drezner. 1984. The p-centre problem\u2014heuristic and optimal algorithms. Journal of the Operational Research Society, 35, 8 (1984), 741\u2013748.","journal-title":"Journal of the Operational Research Society"},{"key":"e_1_3_2_1_21_1","volume-title":"Facility location: applications and theory","author":"Drezner Zvi","unstructured":"Zvi Drezner and Horst W Hamacher. 2004. Facility location: applications and theory. Springer Science & Business Media."},{"key":"e_1_3_2_1_22_1","volume-title":"Stork","author":"Duda Richard O.","year":"2006","unstructured":"Richard O. Duda, Peter E. Hart, and David G. Stork. 2006. Pattern classification. Wiley-India."},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Michael E. Saks (Ed.). ACM\/SIAM, 131\u2013138","author":"Eppstein David","year":"1997","unstructured":"David Eppstein. 1997. Faster Construction of Planar Two-Centers. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Michael E. Saks (Ed.). ACM\/SIAM, 131\u2013138. http:\/\/dl.acm.org\/citation.cfm?id=314161.314198"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62255"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00683-w"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.46298\/THEORETICS.25.4"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v16i1a1"},{"key":"e_1_3_2_1_28_1","volume-title":"On a class of O(n^2) problems in computational geometry. Computational geometry, 5, 3","author":"Gajentaan Anka","year":"1995","unstructured":"Anka Gajentaan and Mark H Overmars. 1995. On a class of O(n^2) problems in computational geometry. Computational geometry, 5, 3 (1995), 165\u2013185."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.10.2.180"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5933"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185335"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.178038"},{"key":"e_1_3_2_1_36_1","volume-title":"Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics, 26, 189-206","author":"Johnson William B","year":"1984","unstructured":"William B Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics, 26, 189-206 (1984), 1."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268649"},{"key":"e_1_3_2_1_38_1","article-title":"Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies","volume":"9","author":"Krause Andreas","year":"2008","unstructured":"Andreas Krause, Ajit Singh, and Carlos Guestrin. 2008. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies.. Journal of Machine Learning Research, 9, 2 (2008).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX). 45\u201355","author":"Kumar Piyush","year":"2003","unstructured":"Piyush Kumar, Joseph SB Mitchell, and E Alper Yildirim. 2003. Computing Core-Sets and Approximate Smallest Enclosing HyperSpheres in High Dimensions.. In Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX). 45\u201355."},{"key":"e_1_3_2_1_40_1","volume-title":"Mining of massive data sets","author":"Leskovec Jure","unstructured":"Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. 2020. Mining of massive data sets. Cambridge university press."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_41"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582124"},{"key":"e_1_3_2_1_43_1","unstructured":"Harald R\u00e4cke. 2006. Lecture 12 of Theory of Metric Embeddings. https:\/\/home.ttic.edu\/ harry\/teaching\/pdf\/lecture12.pdf"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139058452"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009311"},{"key":"e_1_3_2_1_46_1","volume-title":"Pattern recognition","author":"Theodoridis Sergios","unstructured":"Sergios Theodoridis and Konstantinos Koutroumbas. 2006. Pattern recognition. Elsevier."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799352735"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-021-00358-5"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800753","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800753","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:59:52Z","timestamp":1781027992000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":48,"alternative-id":["10.1145\/3798129.3800753","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800753","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}