{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T14:26:05Z","timestamp":1777559165942,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T00:00:00Z","timestamp":1746662400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T00:00:00Z","timestamp":1746662400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,8]]},"DOI":"10.1007\/s00453-025-01317-9","type":"journal-article","created":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T06:50:42Z","timestamp":1746687042000},"page":"1178-1198","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Clustering What Matters in Constrained Settings"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-4475-0922","authenticated-orcid":false,"given":"Ragesh","family":"Jaiswal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3965-6627","authenticated-orcid":false,"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,8]]},"reference":[{"key":"1317_CR1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798602","author":"G Aggarwal","year":"2010","unstructured":"Aggarwal, G., Panigrahy, R., Feder, T., Thomas, D., Kenthapadi, K., Khuller, S., Zhu, A.: Achieving anonymity via clustering. ACM Trans. Algorithms (2010). https:\/\/doi.org\/10.1145\/1798596.1798602","journal-title":"ACM Trans. Algorithms"},{"key":"1317_CR2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.14883","author":"A Agrawal","year":"2023","unstructured":"Agrawal, A., Inamdar, T., Saurabh, S., Xue, J.: Clustering what matters: optimal approximation for clustering with outliers. J. Artif. Int. Res. (2023). https:\/\/doi.org\/10.1613\/jair.1.14883","journal-title":"J. Artif. Int. Res."},{"key":"1317_CR3","doi-asserted-by":"publisher","unstructured":"Ahmadian, S., Norouzi-Fard, A., Svensson, O., Ward, J.: Better guarantees for k-means and euclidean k-median by primal-dual algorithms. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 61\u201372, (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.15","DOI":"10.1109\/FOCS.2017.15"},{"issue":"3","key":"1317_CR4","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"Vijay Arya","year":"2004","unstructured":"Arya, Vijay, Garg, Naveen, Khandekar, Rohit, Meyerson, Adam, Munagala, Kamesh, Pandit, Vinayaka: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004). https:\/\/doi.org\/10.1137\/S0097539702416402","journal-title":"SIAM J. Comput."},{"key":"1317_CR5","doi-asserted-by":"publisher","unstructured":"Bandyapadhyay, S., Fomin, F.V., Simonov, K.: On coresets for fair clustering in metric and euclidean spaces and their applications. In: Bansal, N., Merelli, E., Worrell, J. (eds.), 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 23:1\u201323:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/14092, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.23","DOI":"10.4230\/LIPIcs.ICALP.2021.23"},{"key":"1317_CR6","unstructured":"Bera, S., Chakrabarty, D., Flores, N., Negahbani, M.: Fair algorithms for clustering. In: Wallach, H., Larochelle, H., Beygelzimer, A., d\u2019Alch\u00e9 Buc, F., Fox, E., Garnett, R. (eds.), Advances in Neural Information Processing Systems, vol.\u00a032. Curran Associates, Inc., 2019. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2019\/file\/fc192b0c0d270dbf41870a63a8c76c2f-Paper.pdf"},{"key":"1317_CR7","doi-asserted-by":"publisher","unstructured":"Bercea, I.O., Gro\u00df, M., Khuller, S., Kumar, A., R\u00f6sner, C., Schmidt, D.R., Schmidt, M.: On the Cost of Essentially Fair Clusterings. In: Achlioptas, D., V\u00e9gh, L.A. (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 18:1\u201318:22, Dagstuhl, Germany, 2019. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. URL: http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/11233, https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2019.18","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2019.18"},{"key":"1317_CR8","doi-asserted-by":"publisher","unstructured":"Bhattacharya, A., Goyal, D., Jaiswal, R., Kumar, A.: On sampling based algorithms for k-means. In: Saxena, N., Simon, S. (eds.), 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), volume 182 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 13:1\u201313:17, Dagstuhl, Germany (2020). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. URL: https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/13254, https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2020.13","DOI":"10.4230\/LIPIcs.FSTTCS.2020.13"},{"issue":"1","key":"1317_CR9","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00224-017-9820-7","volume":"62","author":"Anup Bhattacharya","year":"2018","unstructured":"Bhattacharya, Anup, Jaiswal, Ragesh, Kumar, Amit: Faster algorithms for the constrained k-means problem. Theor. Comp. Sys. 62(1), 93\u2013115 (2018). https:\/\/doi.org\/10.1007\/s00224-017-9820-7","journal-title":"Theor. Comp. Sys."},{"key":"1317_CR10","doi-asserted-by":"publisher","unstructured":"Braverman, V., Cohen-Addad, V., Jiang, H., Krauthgamer, R., Schwiegelshohn, C., Toftrup, M., Wu, X.: The power of uniform sampling for coresets. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 462\u2013473, Los Alamitos, CA, USA, (nov 2022). IEEE Computer Society. https:\/\/doi.ieeecomputersociety.org\/10.1109\/FOCS54457.2022.00051, https:\/\/doi.org\/10.1109\/FOCS54457.2022.00051","DOI":"10.1109\/FOCS54457.2022.00051"},{"key":"1317_CR11","doi-asserted-by":"publisher","unstructured":"Chakraborty, Diptarka, Das, Debarati, Krauthgamer, Robert: Clustering permutations: New techniques with streaming applications. In: Kalai, Yael\u00a0Tauman (ed), 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10\u201313, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pp. 31:1\u201331:24. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2023.31","DOI":"10.4230\/LIPIcs.ITCS.2023.31"},{"issue":"1","key":"1317_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M Charikar","year":"2002","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci. 65(1), 129\u2013149 (2002). https:\/\/doi.org\/10.1006\/jcss.2002.1882","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1317_CR13","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"Ke Chen","year":"2009","unstructured":"Chen, Ke.: On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput. 39(3), 923\u2013947 (2009). https:\/\/doi.org\/10.1137\/070699007","journal-title":"SIAM J. Comput."},{"key":"1317_CR14","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Gupta, A., Kumar, A., Lee, E., Li, J.: Tight FPT Approximations for k-Median and k-Means. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 42:1\u201342:14, Dagstuhl, Germany (2019). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. URL: http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10618, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.42","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"1317_CR15","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Li, J.: On the fixed-parameter tractability of capacitated clustering. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 41:1\u201341:14, Dagstuhl, Germany, (2019). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10617, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.41","DOI":"10.4230\/LIPIcs.ICALP.2019.41"},{"key":"1317_CR16","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Saulpic, D., Schwiegelshohn, C.: A new coreset framework for clustering. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pp. 169-182, New York, NY, USA (2021). Association for Computing Machinery. https:\/\/doi.org\/10.1145\/3406325.3451022","DOI":"10.1145\/3406325.3451022"},{"key":"1317_CR17","doi-asserted-by":"crossref","unstructured":"Dabas, R., Gupta, N., Inamdar, T.: FPT approximations for capacitated\/fair clustering with outliers (2023). arXiv:2305.01471","DOI":"10.2139\/ssrn.4781350"},{"key":"1317_CR18","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2020.07.022","volume":"842","author":"H Ding","year":"2020","unstructured":"Ding, H.: Faster balanced clusterings in high dimension. Theor. Comput. Sci. 842, 28\u201340 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.07.022","journal-title":"Theor. Comput. Sci."},{"key":"1317_CR19","doi-asserted-by":"publisher","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for $$k$$-means clustering based on weak coresets. In: Proceedings of the twenty-third annual symposium on Computational geometry, SCG \u201907, pp. 11\u201318, New York, NY, USA (2007). ACM. https:\/\/doi.org\/10.1145\/1247069.1247072","DOI":"10.1145\/1247069.1247072"},{"key":"1317_CR20","doi-asserted-by":"publisher","unstructured":"Goyal, D., Jaiswal, R., Kumar, A.: FPT Approximation for Constrained Metric k-Median\/Means. In: Cao, Y., Pilipczuk, M. (eds.), 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), volume 180 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 14:1\u201314:19, Dagstuhl, Germany, (2020). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. URL: https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/13317, https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.14","DOI":"10.4230\/LIPIcs.IPEC.2020.14"},{"key":"1317_CR21","doi-asserted-by":"publisher","DOI":"10.1145\/2854153","author":"M Hajiaghayi","year":"2016","unstructured":"Hajiaghayi, M., Wei, H., Li, J., Li, S., Saha, B.: A constant factor approximation algorithm for fault-tolerant k-median. ACM Trans. Algorithms (2016). https:\/\/doi.org\/10.1145\/2854153","journal-title":"ACM Trans. Algorithms"},{"key":"1317_CR22","unstructured":"Huang, L., Jiang, S.H.C., Lou, J., Wu, X.: Near-optimal coresets for robust clustering (2022). arXiv:2210.10394"},{"key":"1317_CR23","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-030-39479-0_13","volume-title":"Approximation and Online Algorithms","author":"T Inamdar","year":"2020","unstructured":"Inamdar, T., Varadarajan, K.: Fault tolerant clustering with outliers. In: Bampis, E., Megow, N. (eds.) Approximation and Online Algorithms, pp. 188\u2013201. Springer International Publishing, Cham (2020)"},{"key":"1317_CR24","doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Kumar, A., Nagarajan, V., Sabharwal, Y., Saha, B.: The matroid median problem. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201911, pp. 1117\u20131130, Society for Industrial and Applied Mathematics, USA (2011)","DOI":"10.1137\/1.9781611973082.84"},{"key":"1317_CR25","doi-asserted-by":"publisher","unstructured":"Krishnaswamy, R., Li, S., Sandeep, S.: Constant approximation for k-median and k-means with outliers via iterative rounding. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 646-659, New York, NY, USA (2018). Association for Computing Machinery. https:\/\/doi.org\/10.1145\/3188745.3188882","DOI":"10.1145\/3188745.3188882"},{"issue":"2","key":"1317_CR26","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/1667053.1667054","volume":"57","author":"Amit Kumar","year":"2010","unstructured":"Kumar, Amit, Sabharwal, Yogish, Sen, Sandeep: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), 5:1-5:32 (2010). https:\/\/doi.org\/10.1145\/1667053.1667054","journal-title":"J. ACM"},{"key":"1317_CR27","doi-asserted-by":"publisher","unstructured":"R\u00f6sner, C., Schmidt, M.: Privacy preserving clustering with constraints. In: Chatzigiannakis I., Christos, K., Marx D\u00e1niel, S.D. (eds.), 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 96:1\u201396:14, Dagstuhl, Germany (2018). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. URL: http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9100, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.96","DOI":"10.4230\/LIPIcs.ICALP.2018.96"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01317-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01317-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01317-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T13:42:18Z","timestamp":1757166138000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01317-9"}},"subtitle":["(Improved Outlier to Outlier-Free Reductions)"],"short-title":[],"issued":{"date-parts":[[2025,5,8]]},"references-count":27,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["1317"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01317-9","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3819915\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,8]]},"assertion":[{"value":"29 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Ragesh Jaiswal acknowledges the support from the SERB, MATRICS grant.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}}]}}