{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T19:54:20Z","timestamp":1778702060549,"version":"3.51.4"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T00:00:00Z","timestamp":1678320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1535989"],"award-info":[{"award-number":["CCF-1535989"]}]},{"name":"NSF","award":["CCF-1535972"],"award-info":[{"award-number":["CCF-1535972"]}]},{"name":"NSF","award":["CCF-1535972, CCF-1955703"],"award-info":[{"award-number":["CCF-1535972, CCF-1955703"]}]},{"name":"NSF CAREER","award":["CCF-1750140"],"award-info":[{"award-number":["CCF-1750140"]}]},{"name":"Indo-US Virtual Networked Joint Center on Algorithms"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>This article presents<jats:italic>universal<\/jats:italic>algorithms for clustering problems, including the widely studied<jats:italic>k<\/jats:italic>-median,<jats:italic>k<\/jats:italic>-means, and<jats:italic>k<\/jats:italic>-center objectives. The input is a metric space containing all<jats:italic>potential<\/jats:italic>client locations. The algorithm must select<jats:italic>k<\/jats:italic>cluster centers such that they are a good solution for<jats:italic>any<\/jats:italic>subset of clients that actually realize. Specifically, we aim for low<jats:italic>regret<\/jats:italic>, defined as the maximum over all subsets of the difference between the cost of the algorithm\u2019s solution and that of an optimal solution. A universal algorithm\u2019s solution<jats:sc>Sol<\/jats:sc>for a clustering problem is said to be an \u03b1 , \u03b2-approximation if for all subsets of clients<jats:italic>C<jats:sup>\u2032<\/jats:sup><\/jats:italic>, it satisfies<jats:sc>sol<\/jats:sc>(<jats:italic>C<\/jats:italic><jats:sup>\u2032<\/jats:sup>) \u2264 \u03b1 \u010b<jats:sc>opt<\/jats:sc>(<jats:italic>C<\/jats:italic>\u2032) + \u03b2 \u010b<jats:sc>mr<\/jats:sc>, where<jats:sc>opt<\/jats:sc>(<jats:italic>C<\/jats:italic>\u2032 is the cost of the optimal solution for clients (<jats:italic>C<\/jats:italic>\u2032) and<jats:sc>mr<\/jats:sc>is the minimum regret achievable by any solution.<\/jats:p><jats:p>Our main results are universal algorithms for the standard clustering objectives of<jats:italic>k<\/jats:italic>-median,<jats:italic>k<\/jats:italic>-means, and<jats:italic>k<\/jats:italic>-center that achieve (<jats:italic>O<\/jats:italic>(1),<jats:italic>O<\/jats:italic>(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other \u2113<jats:italic><jats:sub>p<\/jats:sub><\/jats:italic>-objectives and the setting where some subset of the clients are<jats:italic>fixed<\/jats:italic>. We also give hardness results showing that (\u03b1, \u03b2)-approximation is NP-hard if \u03b1 or \u03b2 is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (<jats:italic>O<\/jats:italic>(1),<jats:italic>O<\/jats:italic>(1))-approximation is the strongest type of guarantee obtainable for universal clustering.<\/jats:p>","DOI":"10.1145\/3572840","type":"journal-article","created":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T12:22:21Z","timestamp":1670934141000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Universal Algorithms for Clustering Problems"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6057-7619","authenticated-orcid":false,"given":"Arun","family":"Ganesh","sequence":"first","affiliation":[{"name":"UC Berkeley, Berkeley, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5692-7062","authenticated-orcid":false,"given":"Bruce M.","family":"Maggs","sequence":"additional","affiliation":[{"name":"Duke University and Emerald Innovations, Durham, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1799-6660","authenticated-orcid":false,"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, Durham, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.15"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/142675.142744","volume-title":"Proceedings of the 8th Annual Symposium on Computational Geometry","author":"Alon N.","year":"1992","unstructured":"N. Alon and Y. Azar. 1992. On-line steiner trees in the Euclidean plane. In Proceedings of the 8th Annual Symposium on Computational Geometry. 337\u2013343."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0428"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_6"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276718"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380755"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0966-8349(98)00033-3"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.2.104.11897"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90047-3"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-642-22935-0_7","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Bhalgat Anand","year":"2011","unstructured":"Anand Bhalgat, Deeparnab Chakrabarty, and Sanjeev Khanna. 2011. Optimal lower bounds for universal and differentially private Steiner trees and TSPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and Jos\u00e9 D. P. Rolim (Eds.). Springer, Berlin, 75\u201386."},{"key":"e_1_3_3_12_2","first-page":"51","volume-title":"Proceedings of the 14th Scandanavian Workshop on Algorithm Theory","author":"Bhattacharya Sayan","year":"1994","unstructured":"Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann. 1994. New approximability results for the robust k-median problem. In Proceedings of the 14th Scandanavian Workshop on Algorithm Theory. 51\u201360."},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1109\/FOCS.2012.45","volume-title":"Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201912)","author":"Busch Costas","year":"2012","unstructured":"Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, and Srinivasagopalan Srivathsan. 2012. Split and join: Strong partitions and universal Steiner trees for graphs. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201912). 81\u201390."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316322"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_22"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301257"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1324215.1324236"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1109\/SFCS.2005.42","volume-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905)","author":"Dhamdhere Kedar","year":"2005","unstructured":"Kedar Dhamdhere, Vineet Goyal, R. Ravi, and Mohit Singh. 2005. How to pay, come what may: Approximation algorithms for demand-robust covering problems. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905). 367\u2013378."},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/978-3-540-72792-7_33","volume-title":"Proceedings of the Integer Programming and Combinatorial Optimization","author":"Feige Uriel","year":"2007","unstructured":"Uriel Feige, Kamal Jain, Mohammad Mahdian, and Vahab S. Mirrokni. 2007. Robust combinatorial optimization with exponential scenarios. In Proceedings of the Integer Programming and Combinatorial Optimization. 439\u2013453."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/978-3-642-15369-3_14","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Gorodezky Igor","year":"2010","unstructured":"Igor Gorodezky, Robert D. Kleinberg, David B. Shmoys, and Gwen Spencer. 2010. Improved lower bounds for the universal and a priori TSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Maria Serna, Ronen Shaltiel, Klaus Jansen, and Jos\u00e9 Rolim (Eds.). Springer, Berlin, 178\u2013191."},{"key":"e_1_3_3_24_2","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science","author":"Grandoni F.","year":"2008","unstructured":"F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski, and M. Singh. 2008. Set covering with our eyes closed. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559836"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109665"},{"issue":"1","key":"e_1_3_3_28_2","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s10107-013-0705-5","article-title":"Thresholded covering algorithms for robust and max-min optimization","volume":"146","author":"Gupta Anupam","year":"2014","unstructured":"Anupam Gupta, Viswanath Nagarajan, and R. Ravi. 2014. Thresholded covering algorithms for robust and max-min optimization. Math. Program. 146, 1-2 (2014), 583\u2013615.","journal-title":"Math. Program."},{"issue":"1","key":"e_1_3_3_29_2","first-page":"10:1\u201310:21","article-title":"Robust and MaxMin optimization under matroid and knapsack uncertainty sets","volume":"12","author":"Gupta Anupam","year":"2016","unstructured":"Anupam Gupta, Viswanath Nagarajan, and R. Ravi. 2016. Robust and MaxMin optimization under matroid and knapsack uncertainty sets. ACM Trans. Algor. 12, 1 (2016), 10:1\u201310:21.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007419"},{"key":"e_1_3_3_31_2","article-title":"Simpler analyses of local search algorithms for facility location","volume":"0809","author":"Gupta Anupam","year":"2008","unstructured":"Anupam Gupta and Kanat Tangwongsan. 2008. Simpler analyses of local search algorithms for facility location. arXiv: 0809.2554. Retrieved from https:\/\/arxiv.org\/abs\/0809.2554.","journal-title":"arXiv"},{"key":"e_1_3_3_32_2","first-page":"649","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Hajiaghayi Mohammad T.","year":"2006","unstructured":"Mohammad T. Hajiaghayi, Robert Kleinberg, and Tom Leighton. 2006. Improved lower and upper bounds for universal TSP in planar metrics. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. 649\u2013658."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5933"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_3_3_36_2","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"Jia L.","year":"2005","unstructured":"L. Jia, G. Lin, G. Noubir, R. Rajaraman, and R. Sundaram. 2005. Universal algorithms for TSP, Steiner tree, and set cover. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing."},{"key":"e_1_3_3_37_2","first-page":"282","volume-title":"Distributed Computing in Sensor Systems","author":"Jia Lujun","year":"2006","unstructured":"Lujun Jia, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. 2006. GIST: Group-independent spanning tree for data aggregation in dense sensor networks. In Distributed Computing in Sensor Systems, Phillip B. Gibbons, Tarek Abdelzaher, James Aspnes, and Ramesh Rao (Eds.). Springer, Berlin, 282\u2013304."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513402"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.09.007"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9596-0"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329776"},{"key":"e_1_3_3_42_2","first-page":"378","volume-title":"Proceedings of the Annual European Symposium on Algorithms (ESA\u201999)","author":"Kolliopoulos Stavros G.","year":"1999","unstructured":"Stavros G. Kolliopoulos and Satish Rao. 1999. A nearly linear-time approximation scheme for the Euclidean k-median problem. In Proceedings of the Annual European Symposium on Algorithms (ESA\u201999), Jaroslav Ne\u0161et\u0159il (Ed.). Springer, Berlin, 378\u2013389."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2620-6_6"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.7"},{"key":"e_1_3_3_45_2","first-page":"901","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing","author":"Li Shi","year":"2013","unstructured":"Shi Li and Ola Svensson. 2013. Approximating k-median via pseudo-approximation. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 901\u2013910."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_3_3_47_2","unstructured":"Stuart G. Mentzer. 2016. Approximability of Metric Clustering Problems (unpublished)."},{"key":"e_1_3_3_48_2","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-642-36694-9_25","volume-title":"Integer Programming and Combinatorial Optimization","author":"Nagarajan Viswanath","year":"2013","unstructured":"Viswanath Nagarajan, Baruch Schieber, and Hadas Shachnai. 2013. The Euclidean k-supplier problem. In Integer Programming and Combinatorial Optimization, Michel Goemans and Jos\u00e9 Correa (Eds.). Springer, Berlin, 290\u2013301."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76361"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.04.009"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217860"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1122480.1122493"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1137\/100789269"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3572840","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3572840","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:09Z","timestamp":1750183689000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3572840"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,9]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3572840"],"URL":"https:\/\/doi.org\/10.1145\/3572840","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,9]]},"assertion":[{"value":"2021-10-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-06","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}