{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:07:01Z","timestamp":1765544821425,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T00:00:00Z","timestamp":1644537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MIUR PRIN","award":["2017K7XPAN"],"award-info":[{"award-number":["2017K7XPAN"]}]},{"name":"MIUR","award":["Dipartimenti di eccellenza 2018-2022"],"award-info":[{"award-number":["Dipartimenti di eccellenza 2018-2022"]}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Focused Research Award"],"award-info":[{"award-number":["Focused Research Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BiCi ? Bertinoro international Center for informatics"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,2,11]]},"DOI":"10.1145\/3488560.3498485","type":"proceedings-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T21:42:57Z","timestamp":1644961377000},"page":"5-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["k-Clustering with Fair Outliers"],"prefix":"10.1145","author":[{"given":"Matteo","family":"Almanza","sequence":"first","affiliation":[{"name":"Sapienza University, Rome, Italy"}]},{"given":"Alessandro","family":"Epasto","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY, USA"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[{"name":"Sapienza University, Rome, Italy"}]},{"given":"Giuseppe","family":"Re","sequence":"additional","affiliation":[{"name":"Sapienza University, Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2022,2,15]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Fair clustering via equitable group representations. arXiv:2006.11009","author":"Abbasi Mohsen","year":"2020","unstructured":"Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. 2020. Fair clustering via equitable group representations. arXiv:2006.11009 (2020)."},{"volume-title":"Adaptive sampling for k-means clustering","author":"Aggarwal Ankit","key":"e_1_3_2_2_2_1","unstructured":"Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. 2009. Adaptive sampling for k-means clustering. In APPROX. Springer, 15--28."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Sara Ahmadian Alessandro Epasto Ravi Kumar and Mohammad Mahdian. 2019. Clustering without over-representation. In KDD. 267--275.","DOI":"10.1145\/3292500.3330987"},{"key":"e_1_3_2_2_4_1","unstructured":"Sara Ahmadian Alessandro Epasto Ravi Kumar and Mohammad Mahdian. 2020. Fair Correlation clustering. In AISTATS ."},{"volume-title":"IPCO","author":"Anegg Georg","key":"e_1_3_2_2_5_1","unstructured":"Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen. 2020. A Technique for Obtaining True Approximations for k-Center with Covering Constraints. In IPCO . Springer, 52--65."},{"key":"e_1_3_2_2_7_1","volume-title":"Scalable fair clustering. arXiv:1902.03519","author":"Backurs Arturs","year":"2019","unstructured":"Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. 2019. Scalable fair clustering. arXiv:1902.03519 (2019)."},{"key":"e_1_3_2_2_8_1","volume-title":"Scalable k-means++. arXiv:1203.6402","author":"Bahmani Bahman","year":"2012","unstructured":"Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii. 2012. Scalable k-means++. arXiv:1203.6402 (2012)."},{"key":"e_1_3_2_2_9_1","volume-title":"Fairness and Outliers. arXiv preprint arXiv:2103.03337","author":"Bajpai Tanvi","year":"2021","unstructured":"Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, and Maryam Negahbani. 2021. Revisiting Priority $ k $-Center: Fairness and Outliers. arXiv preprint arXiv:2103.03337 (2021)."},{"key":"e_1_3_2_2_10_1","unstructured":"Sayan Bandyapadhyay Tanmay Inamdar Shreyas Pai and Kasturi Varadarajan. 2019. A Constant Approximation for Colorful k-Center. In ESA ."},{"key":"e_1_3_2_2_11_1","unstructured":"Solon Barocas Moritz Hardt and Arvind Narayanan. 2019. Fairness and Machine Learning .fairmlbook.org. http:\/\/www.fairmlbook.org ."},{"key":"e_1_3_2_2_12_1","unstructured":"Suman Bera Deeparnab Chakrabarty Nicolas Flores and Maryam Negahbani. 2019. Fair algorithms for clustering. In NeurIPS. 4954--4965."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.04.006"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Alina Beygelzimer Sham Kakade and John Langford. 2006. Cover trees for nearest neighbor. In ICML. 97--104.","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_3_2_2_15_1","unstructured":"Aditya Bhaskara and Aravinda Kanchana Rwanpathirana. 2020. Robust Algorithms for Online $ k $-means Clustering. In ALT. 148--173."},{"key":"e_1_3_2_2_16_1","unstructured":"Aditya Bhaskara Sharvaree Vadgama and Hong Xu. 2019. Greedy Sampling for Approximate Clustering in the Presence of Outliers. In NeurIPS . 11146--11155."},{"key":"e_1_3_2_2_17_1","unstructured":"Nitin Bhatia et al. 2010. Survey of nearest neighbor techniques. arXiv:1007.0085 (2010)."},{"volume-title":"Adverse impact and test validation: A practitioner's guide to valid and defensible employment testing .Gower Pub","author":"Biddle Dan","key":"e_1_3_2_2_18_1","unstructured":"Dan Biddle. 2006. Adverse impact and test validation: A practitioner's guide to valid and defensible employment testing .Gower Pub. Ltd."},{"volume-title":"Theoretical Analysis of the k-Means Algorithm -- A Survey","author":"Bl\u00f6mer Johannes","key":"e_1_3_2_2_19_1","unstructured":"Johannes Bl\u00f6mer, Christiane Lammersen, Melanie Schmidt, and Christian Sohler. 2016. Theoretical Analysis of the k-Means Algorithm -- A Survey .Springer, 81--116."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"crossref","unstructured":"TH Hubert Chan Arnaud Guerqin and Mauro Sozio. 2018. Fully dynamic k-center clustering. In WWW. 579--587.","DOI":"10.1145\/3178876.3186124"},{"volume-title":"Algorithms for facility location problems with outliers","author":"Charikar Moses","key":"e_1_3_2_2_21_1","unstructured":"Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan. 2001. Algorithms for facility location problems with outliers. In SODA. SIAM, 642--651."},{"volume-title":"k-means--: A unified approach to clustering and outlier detection","author":"Chawla Sanjay","key":"e_1_3_2_2_22_1","unstructured":"Sanjay Chawla and Aristides Gionis. 2013. k-means--: A unified approach to clustering and outlier detection. In SDM. SIAM, 189--197."},{"key":"e_1_3_2_2_23_1","unstructured":"Jiecao Chen Erfan S Azer and Qin Zhang. 2018. A practical algorithm for distributed clustering and outlier detection. In NeurIPS . 2248--2256."},{"key":"e_1_3_2_2_24_1","unstructured":"Ke Chen. 2008. A constant factor approximation algorithm for k-median clustering with outliers. In SODA . 826--835."},{"key":"e_1_3_2_2_25_1","unstructured":"Flavio Chierichetti Ravi Kumar Silvio Lattanzi and Sergei Vassilvitskii. 2017. Fair clustering through fairlets. In NIPS. 5029--5037."},{"key":"e_1_3_2_2_26_1","volume-title":"The measure and mismeasure of fairness: A critical review of fair machine learning. arXiv:1808.00023","author":"Corbett-Davies Sam","year":"2018","unstructured":"Sam Corbett-Davies and Sharad Goel. 2018. The measure and mismeasure of fairness: A critical review of fair machine learning. arXiv:1808.00023 (2018)."},{"key":"e_1_3_2_2_27_1","unstructured":"Amit Deshpande Praneeth Kacham and Rameshwar Pratap. 2020. Robust k-means++. In UAI. PMLR 799?808."},{"key":"e_1_3_2_2_28_1","unstructured":"Hu Ding Haikuo Yu and Zixiu Wang. 2019. Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction. In ESA ."},{"key":"e_1_3_2_2_29_1","unstructured":"Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Moritz Hardt Toniann Pitassi Omer Reingold and Richard Zemel. 2012. Fairness through awareness. In ITCS. 214--226.","DOI":"10.1145\/2090236.2090255"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Michael Feldman Sorelle A Friedler John Moeller Carlos Scheidegger and Suresh Venkatasubramanian. 2015. Certifying and removing disparate impact. In KDD .","DOI":"10.1145\/2783258.2783311"},{"key":"e_1_3_2_2_32_1","volume-title":"Approximation schemes for clustering with outliers. TALG","author":"Friggstad Zachary","year":"2019","unstructured":"Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R Salavatipour. 2019. Approximation schemes for clustering with outliers. TALG (2019)."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Mehrdad Ghadiri Samira Samadi and Santosh Vempala. 2021. Socially fair k-means clustering. In FAccT. 438--448.","DOI":"10.1145\/3442188.3445906"},{"key":"e_1_3_2_2_34_1","first-page":"757","article-title":"Local search methods for k-means with outliers","volume":"10","author":"Gupta Shalmoli","year":"2017","unstructured":"Shalmoli Gupta, Ravi Kumar, Kefu Lu, Benjamin Moseley, and Sergei Vassilvitskii. 2017. Local search methods for k-means with outliers. VLDB , Vol. 10, 7 (2017), 757--768.","journal-title":"VLDB"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Sariel Har-Peled. 2011. Geometric approximation algorithms . Number 173. AMS.","DOI":"10.1090\/surv\/173"},{"key":"e_1_3_2_2_36_1","first-page":"3315","article-title":"Equality of Opportunity in Supervised Learning","volume":"29","author":"Hardt Moritz","year":"2016","unstructured":"Moritz Hardt, Eric Price, and Nati Srebro. 2016. Equality of Opportunity in Supervised Learning. NIPS , Vol. 29 (2016), 3315--3323.","journal-title":"NIPS"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3311953","article-title":"A lottery model for center-type problems with outliers","volume":"15","author":"Harris David G","year":"2019","unstructured":"David G Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. 2019. A lottery model for center-type problems with outliers. TALG , Vol. 15, 3 (2019), 1--25.","journal-title":"TALG"},{"volume-title":"Fast Noise Removal for k-Means Clustering (PMLR","author":"Im Sungjin","key":"e_1_3_2_2_38_1","unstructured":"Sungjin Im, Mahshid M Qaem, Benjamin Moseley, Xiaorui Sun, and Rudy Zhou. 2020. Fast Noise Removal for k-Means Clustering (PMLR, Vol. 108). 456--466."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_2_40_1","volume-title":"On the Partition Set Cover Problem. arXiv:1809.06506","author":"Inamdar Tanmay","year":"2018","unstructured":"Tanmay Inamdar and Kasturi Varadarajan. 2018. On the Partition Set Cover Problem. arXiv:1809.06506 (2018)."},{"key":"e_1_3_2_2_41_1","volume-title":"Data clustering: 50 years beyond K-means. Pattern recognition letters","author":"Jain Anil K","year":"2010","unstructured":"Anil K Jain. 2010. Data clustering: 50 years beyond K-means. Pattern recognition letters , Vol. 31, 8 (2010), 651--666."},{"volume-title":"Fair Colorful k-Center Clustering","author":"Jia Xinrui","key":"e_1_3_2_2_42_1","unstructured":"Xinrui Jia, Kshiteej Sheth, and Ola Svensson. 2020. Fair Colorful k-Center Clustering. In IPCO. Springer, 209--222."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Tapas Kanungo David M Mount Nathan S Netanyahu Christine D Piatko Ruth Silverman and Angela Y Wu. 2002. A local search approximation algorithm for k-means clustering. In SOCG. 10--18.","DOI":"10.1145\/513400.513402"},{"volume-title":"The ethical algorithm: The science of socially aware algorithm design","author":"Kearns Michael","key":"e_1_3_2_2_44_1","unstructured":"Michael Kearns and Aaron Roth. 2019. The ethical algorithm: The science of socially aware algorithm design .Oxford University Press."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Aria Khademi Sanghack Lee David Foley and Vasant Honavar. 2019. Fairness in algorithmic decision making: An excursion through the lens of causality. In WWW . 2907--2914.","DOI":"10.1145\/3308558.3313559"},{"key":"e_1_3_2_2_46_1","volume-title":"Fair k-center clustering for data summarization. arXiv:1901.08628","author":"Awasthi Pranjal","year":"2019","unstructured":"Matth\"aus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. 2019. Fair k-center clustering for data summarization. arXiv:1901.08628 (2019)."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Emmanouil Krasanakis Eleftherios Spyromitros-Xioufis Symeon Papadopoulos and Yiannis Kompatsiaris. 2018. Adaptive sensitive reweighting to mitigate bias in fairness-aware classification. In WWW . 853--862.","DOI":"10.1145\/3178876.3186133"},{"key":"e_1_3_2_2_48_1","unstructured":"Robert Krauthgamer and James R Lee. 2004. Navigating nets: Simple algorithms for proximity search. In SODA. Citeseer 798--807."},{"key":"e_1_3_2_2_49_1","unstructured":"Silvio Lattanzi and Sergei Vassilvitskii. 2017. Consistent k-clustering. In ICML ."},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938645"},{"key":"e_1_3_2_2_51_1","unstructured":"Daniel Lokshtanov Chinmay Sonar Subhash Suri and Jie Xue. 2020. Fair Covering of Points by Balls. (2020)."},{"key":"e_1_3_2_2_52_1","unstructured":"Sepideh Mahabadi and Ali Vakilian. 2020. Individual fairness for k-clustering. In ICML. PMLR 6586--6596."},{"key":"e_1_3_2_2_53_1","volume-title":"A k-median algorithm with running time independent of data size. Machine Learning","author":"Meyerson Adam","year":"2004","unstructured":"Adam Meyerson, Liadan O'callaghan, and Serge Plotkin. 2004. A k-median algorithm with running time independent of data size. Machine Learning (2004)."},{"key":"e_1_3_2_2_54_1","volume-title":"Fully proportional representation. American Political Science Review","author":"Monroe Burt L","year":"1995","unstructured":"Burt L Monroe. 1995. Fully proportional representation. American Political Science Review (1995), 925--940."},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2014.03.001"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"crossref","unstructured":"Bruno Ordozgoiti and Aristides Gionis. 2019. Reconciliation k-median: Clustering with Non-polarized Representatives. In WWW . 1387--1397.","DOI":"10.1145\/3308558.3313475"},{"key":"e_1_3_2_2_57_1","first-page":"5680","article-title":"On Fairness and Calibration","volume":"30","author":"Pleiss Geoff","year":"2017","unstructured":"Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. 2017. On Fairness and Calibration. NeurIPS , Vol. 30 (2017), 5680--5689.","journal-title":"NeurIPS"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"crossref","unstructured":"Jean Pouget-Abadie Vahab Mirrokni David C Parkes and Edoardo M Airoldi. 2018. Optimizing cluster-based randomized experiments under monotonicity. In KDD . 2090--2099.","DOI":"10.1145\/3219819.3220067"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"crossref","unstructured":"Dongmei Ren Imad Rahal William Perrizo and Kirk Scott. 2004. A vertical distance-based outlier detection method with local pruning. In CIKM . 279--284.","DOI":"10.1145\/1031171.1031232"},{"key":"e_1_3_2_2_60_1","volume-title":"Fair coresets and streaming algorithms for fair k-means clustering. arXiv:1812.10854","author":"Schmidt Melanie","year":"2018","unstructured":"Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. 2018. Fair coresets and streaming algorithms for fair k-means clustering. arXiv:1812.10854 (2018)."},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"crossref","unstructured":"Anurag Shandilya Kripabandhu Ghosh and Saptarshi Ghosh. 2018. Fairness of Extractive Text Summarization. In WWW. 97--98.","DOI":"10.1145\/3184558.3186947"},{"key":"e_1_3_2_2_62_1","volume-title":"Cost-based modeling and evaluation for data mining with application to fraud and intrusion detection. Results from the JAM Project by Salvatore","author":"Stolfo J","year":"2000","unstructured":"J Stolfo, Wei Fan, Wenke Lee, Andreas Prodromidis, and Philip K Chan. 2000. Cost-based modeling and evaluation for data mining with application to fraud and intrusion detection. Results from the JAM Project by Salvatore (2000), 1--15."},{"key":"e_1_3_2_2_63_1","volume-title":"Sebastian Ventura, Krzysztof Cios, and John Clore.","author":"Strack Beata","year":"2014","unstructured":"Beata Strack, Jonathan Deshazo, Chris Gennings, Juan Luis Olmo Ortiz, Sebastian Ventura, Krzysztof Cios, and John Clore. 2014. Impact of HbA1c Measurement on Hospital Readmission Rates: Analysis of 70,000 Clinical Database Patient Records. BioMed research international , Vol. 2014 (04 2014), 781670."},{"volume-title":"The design of approximation algorithms","author":"Williamson David P","key":"e_1_3_2_2_64_1","unstructured":"David P Williamson and David B Shmoys. 2011. The design of approximation algorithms .Cambridge University Press."},{"key":"e_1_3_2_2_65_1","first-page":"311","article-title":"Data structures and algorithms for nearest neighbor search in general metric spaces","volume":"93","author":"Yianilos Peter N","year":"1993","unstructured":"Peter N Yianilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. In SODA , Vol. 93. 311--21.","journal-title":"SODA"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"crossref","unstructured":"Hongjing Zhang and Ian Davidson. 2021. Towards Fair Deep Anomaly Detection. In FAccT. 138--148.","DOI":"10.1145\/3442188.3445878"},{"key":"e_1_3_2_2_67_1","volume-title":"Data clustering in life sciences. Mol. biotechnol","author":"Zhao Ying","year":"2005","unstructured":"Ying Zhao and George Karypis. 2005. Data clustering in life sciences. Mol. biotechnol. , Vol. 31, 1 (2005), 55--80."}],"event":{"name":"WSDM '22: The Fifteenth ACM International Conference on Web Search and Data Mining","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data","SIGIR ACM Special Interest Group on Information Retrieval"],"location":"Virtual Event AZ USA","acronym":"WSDM '22"},"container-title":["Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488560.3498485","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3488560.3498485","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:19Z","timestamp":1750188679000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488560.3498485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,11]]},"references-count":66,"alternative-id":["10.1145\/3488560.3498485","10.1145\/3488560"],"URL":"https:\/\/doi.org\/10.1145\/3488560.3498485","relation":{},"subject":[],"published":{"date-parts":[[2022,2,11]]},"assertion":[{"value":"2022-02-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}