{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T00:34:49Z","timestamp":1760056489800,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031931116"},{"type":"electronic","value":"9783031931123"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-93112-3_4","type":"book-chapter","created":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T04:56:18Z","timestamp":1749531378000},"page":"43-57","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Constant-Factor Approximation for\u00a0Pairwise Fair k-Center Clustering"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8875-0102","authenticated-orcid":false,"given":"Sayan","family":"Bandyapadhyay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5581-5834","authenticated-orcid":false,"given":"Tianzhi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4039-3235","authenticated-orcid":false,"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-9937-0208","authenticated-orcid":false,"given":"Mahya","family":"Jamshidian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,4]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Ahmadian, S., Epasto, A., Kumar, R., Mahdian, M.: Clustering without over-representation. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 267\u2013275 (2019)","DOI":"10.1145\/3292500.3330987"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Anegg, G., Angelidakis, H., Kurpisz, A., Zenklusen, R.: A technique for obtaining true approximations for $$k$$-center with covering constraints. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 52\u201365. Springer (2020)","DOI":"10.1007\/978-3-030-45771-6_5"},{"key":"4_CR3","unstructured":"Bandyapadhyay, S., Chlamt\u00e1\u010d, E., Makarychev, Y., Vakilian, A.: A polynomial-time approximation for pairwise fair $$ k $$-median clustering. arXiv preprint arXiv:2405.10378 (2024)"},{"key":"4_CR4","unstructured":"Bandyapadhyay, S., Inamdar, T., Pai, S., Varadarajan, K.: A constant approximation for colorful $$k$$-center. In: 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)"},{"key":"4_CR5","unstructured":"Bera, S., Chakrabarty, D., Flores, N., Negahbani, M.: Fair algorithms for clustering. In: Advances in Neural Information Processing Systems, pp. 4954\u20134965 (2019)"},{"key":"4_CR6","unstructured":"Bercea, I.O., et al.: On the cost of essentially fair clusterings. arXiv preprint arXiv:1811.10319 (2018)"},{"key":"4_CR7","unstructured":"Bercea, I.O., et al.: On the cost of essentially fair clusterings. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM) (2019)"},{"key":"4_CR8","unstructured":"B\u00f6hm, M., Fazzone, A., Leonardi, S., Schwiegelshohn, C.: Fair clustering with multiple colors. arXiv preprint arXiv:2002.07892 (2020)"},{"key":"4_CR9","unstructured":"Brubach, B., Chakrabarti, D., Dickerson, J., Khuller, S., Srinivasan, A., Tsepenekas, L.: A pairwise fair and community-preserving approach to $$k$$-center clustering. In: International Conference on Machine Learning (ICML), pp. 1178\u20131189 (2020)"},{"issue":"4","key":"4_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3392720","volume":"16","author":"D Chakrabarty","year":"2020","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform k-center problem. ACM Trans. Algorithms (TALG) 16(4), 1\u201319 (2020)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Krishnaswamy, R., Kumar, A.: The heterogeneous capacitated k-center problem. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 123\u2013135. Springer (2017)","DOI":"10.1007\/978-3-319-59250-3_11"},{"issue":"3","key":"4_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3338513","volume":"15","author":"D Chakrabarty","year":"2019","unstructured":"Chakrabarty, D., Negahbani, M.: Generalized center problems with outliers. ACM Trans. Algorithms (TALG) 15(3), 1\u201314 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"2","key":"4_CR13","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1007\/s10107-022-01799-3","volume":"197","author":"D Chakrabarty","year":"2023","unstructured":"Chakrabarty, D., Negahbani, M.: Robust k-center with two types of radii. Math. Program. 197(2), 991\u20131007 (2023)","journal-title":"Math. Program."},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Chhabra, A., Masalkovait\u0117, K., Mohapatra, P.: An overview of fairness in clustering. IEEE Access (2021)","DOI":"10.1109\/ACCESS.2021.3114099"},{"key":"4_CR15","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Advances in Neural Information Processing Systems, pp. 5029\u20135037 (2017)"},{"key":"4_CR16","unstructured":"Chiplunkar, A., Kale, S., Ramamoorthy, S.N.: How to solve fair $$k$$-center in massive data models. In: Proceedings of the International Conference on Machine Learning (ICML), pp. 1877\u20131886 (2020)"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M.T., Khuller, S.: LP rounding for k-centers with non-uniform hard capacities. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, 20\u201323 October 2012, pp. 273\u2013282. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.63"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"4_CR19","first-page":"1","volume":"15","author":"DG Harris","year":"2019","unstructured":"Harris, D.G., Pensyl, T., Srinivasan, A., Trinh, K.: A lottery model for center-type problems with outliers. ACM Trans. Algorithms (TALG) 15(3), 1\u201325 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"4_CR20","unstructured":"Hotegni, S.S., Mahabadi, S., Vakilian, A.: Approximation algorithms for fair range clustering. In: International Conference on Machine Learning, pp. 13270\u201313284. PMLR (2023)"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Jia, X., Rohwedder, L., Sheth, K., Svensson, O.: Towards non-uniform k-center with constant types of radii. In: Symposium on Simplicity in Algorithms (SOSA), pp. 228\u2013237. SIAM (2022)","DOI":"10.1137\/1.9781611977066.16"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Jia, X., Sheth, K., Svensson, O.: Fair colorful k-center clustering. Math. Program. 1\u201322 (2021)","DOI":"10.1007\/s10107-021-01674-7"},{"key":"4_CR23","unstructured":"Jones, M., Nguyen, H., Nguyen, T.: Fair $$k$$-centers via maximum matching. In: Proceedings of the International Conference on Machine Learning (ICML), pp. 4940\u20134949 (2020)"},{"issue":"3","key":"4_CR24","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480197329776","volume":"13","author":"S Khuller","year":"2000","unstructured":"Khuller, S., Sussmann, Y.J.: The capacitated K-center problem. SIAM J. Discret. Math. 13(3), 403\u2013418 (2000)","journal-title":"SIAM J. Discret. Math."},{"key":"4_CR25","unstructured":"Kleindessner, M., Awasthi, P., Morgenstern, J.: Fair $$k$$-center clustering for data summarization. In: 36th International Conference on Machine Learning, ICML 2019, pp. 5984\u20136003. International Machine Learning Society (IMLS) (2019)"},{"key":"4_CR26","unstructured":"Negahbani, M., Chakrabarty, D.: Better algorithms for individually fair $$k$$-clustering. In: Advances in Neural Information Processing Systems (NeurIPS), vol. 34, pp. 13340\u201313351 (2021)"},{"key":"4_CR27","unstructured":"R\u00f6sner, C., Schmidt, M.: Privacy preserving clustering with constraints. In: International Colloquium on Automata, Languages, and Programming (ICALP) (2018)"},{"key":"4_CR28","unstructured":"Vakilian, A., Yal\u00e7\u0131ner, M.: Improved approximation algorithms for individually fair clustering. In: International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 8758\u20138779. PMLR (2022)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-93112-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T10:53:29Z","timestamp":1760007209000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-93112-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031931116","9783031931123"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-93112-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"4 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Baltimore, MD","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ipco25.cs.jhu.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}