{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T20:01:03Z","timestamp":1772913663257,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T00:00:00Z","timestamp":1603065600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EC H2020RIA project"},{"name":"MIUR PRIN project ALGADIMAR"},{"name":"ERC Advanced Grant 788893 AMDROMA"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,10,19]]},"DOI":"10.1145\/3340531.3412036","type":"proceedings-article","created":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T05:31:03Z","timestamp":1603085463000},"page":"35-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Spectral Relaxations and Fair Densest Subgraphs"],"prefix":"10.1145","author":[{"given":"Aris","family":"Anagnostopoulos","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]},{"given":"Luca","family":"Becchetti","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]},{"given":"Adriano","family":"Fazzone","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]},{"given":"Cristina","family":"Menghini","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]},{"given":"Chris","family":"Schwiegelshohn","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2020,10,19]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"405","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","author":"Backurs A.","year":"2019","unstructured":"Backurs , A. , Indyk , P. , Onak , K. , Schieber , B. , Vakilian , A. , and Wagner , T . Scalable fair clustering . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , 9-15 June 2019 , Long Beach, California, USA (2019), pp. 405 -- 413 . Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., and Wagner, T. Scalable fair clustering. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA (2019), pp. 405--413."},{"key":"e_1_3_2_2_2_1","first-page":"59","volume-title":"WAW 2014, Beijing, China, December 17-18, 2014","author":"Bahmani B.","year":"2014","unstructured":"Bahmani , B. , Goel , A. , and Munagala , K . Efficient primal-dual graph algorithms for mapreduce. In Algorithms and Models for the Web Graph - 11th International Workshop , WAW 2014, Beijing, China, December 17-18, 2014 , Proceedings ( 2014 ), pp. 59 -- 78 . Bahmani, B., Goel, A., and Munagala, K. Efficient primal-dual graph algorithms for mapreduce. In Algorithms and Models for the Web Graph - 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings (2014), pp. 59--78."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316318"},{"key":"e_1_3_2_2_4_1","first-page":"4955","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Bera S. K.","year":"2019","unstructured":"Bera , S. K. , Chakrabarty , D. , Flores , N. , and Negahbani , M . Fair algorithms for clustering . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019 , 8-14 December 2019, Vancouver, BC, Canada (2019), pp. 4955 -- 4966 . Bera, S. K., Chakrabarty, D., Flores, N., and Negahbani, M. Fair algorithms for clustering. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada (2019), pp. 4955--4966."},{"key":"e_1_3_2_2_5_1","volume-title":"C., Schmidt, D. R., and Schmidt, M. On the cost of essentially fair clusterings. CoRR abs\/1811.10319","author":"Bercea I. O.","year":"2018","unstructured":"Bercea , I. O. , Gro\u00df , M. , Khuller , S. , Kumar , A. , R\u00f6 sner , C., Schmidt, D. R., and Schmidt, M. On the cost of essentially fair clusterings. CoRR abs\/1811.10319 ( 2018 ). Bercea, I. O., Gro\u00df, M., Khuller, S., Kumar, A., R\u00f6 sner, C., Schmidt, D. R., and Schmidt, M. On the cost of essentially fair clusterings. CoRR abs\/1811.10319 (2018)."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.34"},{"key":"e_1_3_2_2_8_1","volume-title":"Fair clustering with multiple colors. CoRR abs\/2002.07892","author":"B\u00f6","year":"2020","unstructured":"B\u00f6 hm, M., Fazzone , A. , Leonardi , S. , and Schwiegelshohn , C . Fair clustering with multiple colors. CoRR abs\/2002.07892 ( 2020 ). B\u00f6 hm, M., Fazzone, A., Leonardi, S., and Schwiegelshohn, C. Fair clustering with multiple colors. CoRR abs\/2002.07892 (2020)."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.3386\/w23258"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/20"},{"key":"e_1_3_2_2_11_1","first-page":"1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"Celis L. E.","year":"2018","unstructured":"Celis , L. E. , Straszak , D. , and Vishnoi , N. K . Ranking with fairness constraints. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018 , Prague, Czech Republic (2018), pp. 28: 1 -- 28 :15. Celis, L. E., Straszak, D., and Vishnoi, N. K. Ranking with fairness constraints. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic (2018), pp. 28:1--28:15."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3091106"},{"key":"e_1_3_2_2_13_1","first-page":"84","volume-title":"Third International Workshop, APPROX 2000, Saarbr\u00fc cken, Germany, September 5-8, 2000","author":"Charikar M.","year":"2000","unstructured":"Charikar , M. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization , Third International Workshop, APPROX 2000, Saarbr\u00fc cken, Germany, September 5-8, 2000 , Proceedings ( 2000 ), pp. 84 -- 95 . Charikar, M. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbr\u00fc cken, Germany, September 5-8, 2000, Proceedings (2000), pp. 84--95."},{"key":"e_1_3_2_2_14_1","first-page":"5036","volume-title":"Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS)","author":"Chierichetti F.","year":"2017","unstructured":"Chierichetti , F. , Kumar , R. , Lattanzi , S. , and Vassilvitskii , S . Fair clustering through fairlets . In Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS) ( 2017 ), pp. 5036 -- 5044 . Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. Fair clustering through fairlets. In Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS) (2017), pp. 5036--5044."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935813"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.103"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783311"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132993"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536342"},{"key":"e_1_3_2_2_23_1","first-page":"3315","volume-title":"Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016","author":"Hardt M.","year":"2016","unstructured":"Hardt , M. , Price , E. , and Srebro , N . Equality of opportunity in supervised learning . In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016 , December 5-10, 2016 , Barcelona, Spain (2016), pp. 3315 -- 3323 . Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain (2016), pp. 3315--3323."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1177\/1534484305275847"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_3_2_2_26_1","first-page":"7587","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Huang L.","year":"2019","unstructured":"Huang , L. , Jiang , S. H. , and Vishnoi , N. K . Coresets for clustering with fairness constraints . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019 , 8-14 December 2019, Vancouver, BC, Canada (2019), H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9 -Buc, E. B. Fox, and R. Garnett, Eds., pp. 7587 -- 7598 . Huang, L., Jiang, S. H., and Vishnoi, N. K. Coresets for clustering with fairness constraints. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada (2019), H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9 -Buc, E. B. Fox, and R. Garnett, Eds., pp. 7587--7598."},{"key":"e_1_3_2_2_27_1","volume-title":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn Bonn","author":"Kannan R.","year":"1999","unstructured":"Kannan , R. , and Vinay , V . Analyzing the structure of large graphs . Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn Bonn , 1999 . Kannan, R., and Vinay, V. Analyzing the structure of large graphs. Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn Bonn, 1999."},{"key":"e_1_3_2_2_28_1","first-page":"3458","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","author":"Kleindessner M.","year":"2019","unstructured":"Kleindessner , M. , Samadi , S. , Awasthi , P. , and Morgenstern , J . Guarantees for spectral clustering with fairness constraints . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , 9-15 June 2019 , Long Beach, California, USA (2019), pp. 3458 -- 3467 . Kleindessner, M., Samadi, S., Awasthi, P., and Morgenstern, J. Guarantees for spectral clustering with fairness constraints. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA (2019), pp. 3458--3467."},{"key":"e_1_3_2_2_29_1","unstructured":"rebs V. Polbook-network-dataset v. krebs unpublished. http:\/\/www.orgnet.com\/.  rebs V. Polbook-network-dataset v. krebs unpublished. http:\/\/www.orgnet.com\/."},{"key":"e_1_3_2_2_30_1","first-page":"467","volume-title":"Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2009), KDD '09","author":"Lappas T.","unstructured":"Lappas , T. , Liu , K. , and Terzi , E . Finding a team of experts in social networks . In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2009), KDD '09 , pp. 467 -- 476 . Lappas, T., Liu, K., and Terzi, E. Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2009), KDD '09, pp. 467--476."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055412"},{"key":"e_1_3_2_2_32_1","volume-title":"Twenty-Third International Joint Conference on Artificial Intelligence","author":"Marcolino L. S.","year":"2013","unstructured":"Marcolino , L. S. , Jiang , A. X. , and Tambe , M . Multi-agent team formation: diversity beats strength? In Twenty-Third International Joint Conference on Artificial Intelligence ( 2013 ). Marcolino, L. S., Jiang, A. X., and Tambe, M. Multi-agent team formation: diversity beats strength? In Twenty-Third International Joint Conference on Artificial Intelligence (2013)."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959929"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186103"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132966"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D19-1018"},{"key":"e_1_3_2_2_37_1","volume-title":"Active fairness in algorithmic decision making. CoRR abs\/1810.00031","author":"Noriega-Campero A.","year":"2018","unstructured":"Noriega-Campero , A. , Bakker , M. , Garcia-Bulle , B. , and Pentland , A . Active fairness in algorithmic decision making. CoRR abs\/1810.00031 ( 2018 ). Noriega-Campero, A., Bakker, M., Garcia-Bulle, B., and Pentland, A. Active fairness in algorithmic decision making. CoRR abs\/1810.00031 (2018)."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_2_39_1","first-page":"1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"R\u00f6","year":"2018","unstructured":"R\u00f6 sner, C., and Schmidt , M . Privacy preserving clustering with constraints. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018 , Prague, Czech Republic (2018), pp. 96: 1 -- 96 :14. R\u00f6 sner, C., and Schmidt, M. Privacy preserving clustering with constraints. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic (2018), pp. 96:1--96:14."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00055"},{"key":"e_1_3_2_2_41_1","first-page":"10999","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Samadi S.","year":"2018","unstructured":"Samadi , S. , Tantipongpipat , U. T. , Morgenstern , J. H. , Singh , M. , and Vempala , S . The price of fair PCA: one extra dimension . In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 , NeurIPS 2018 , 3-8 December 2018, Montr\u00e9 al, Canada. (2018), pp. 10999 -- 11010 . Samadi, S., Tantipongpipat, U. T., Morgenstern, J. H., Singh, M., and Vempala, S. The price of fair PCA: one extra dimension. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montr\u00e9 al, Canada. (2018), pp. 10999--11010."},{"key":"e_1_3_2_2_42_1","first-page":"232","volume-title":"WAOA 2019","author":"Schmidt M.","year":"2019","unstructured":"Schmidt , M. , Schwiegelshohn , C. , and Sohler , C . Fair coresets and streaming algorithms for fair k-means. In Approximation and Online Algorithms - 17th International Workshop , WAOA 2019 , Munich, Germany, September 12--13 , 2019 , Revised Selected Papers (2019), pp. 232 -- 251 . Schmidt, M., Schwiegelshohn, C., and Sohler, C. Fair coresets and streaming algorithms for fair k-means. In Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12--13, 2019, Revised Selected Papers (2019), pp. 232--251."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_3_2_2_44_1","first-page":"15135","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Tantipongpipat U.","year":"2019","unstructured":"Tantipongpipat , U. , Samadi , S. , Singh , M. , Morgenstern , J. H. , and Vempala , S. S . Multi-criteria dimensionality reduction with applications to fairness . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019 , 8-14 December 2019, Vancouver, BC, Canada (2019), H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9 -Buc, E. B. Fox, and R. Garnett, Eds., pp. 15135 -- 15145 . Tantipongpipat, U., Samadi, S., Singh, M., Morgenstern, J. H., and Vempala, S. S. Multi-criteria dimensionality reduction with applications to fairness. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada (2019), H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9 -Buc, E. B. Fox, and R. Garnett, Eds., pp. 15135--15145."},{"key":"e_1_3_2_2_45_1","first-page":"502","volume-title":"Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Thanh B. L.","year":"2011","unstructured":"Thanh , B. L. , Ruggieri , S. , and Turini , F . k-nn as an implementation of situation testing for discrimination discovery and prevention . In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ( 2011 ), pp. 502 -- 510 . Thanh, B. L., Ruggieri, S., and Turini, F. k-nn as an implementation of situation testing for discrimination discovery and prevention. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2011), pp. 502--510."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052660"},{"key":"e_1_3_2_2_48_1","first-page":"962","volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017","author":"Zafar M. B.","year":"2017","unstructured":"Zafar , M. B. , Valera , I. , Gomez-Rodriguez , M. , and Gummadi , K. P . Fairness constraints: Mechanisms for fair classification . In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 , 20-22 April 2017 , Fort Lauderdale, FL, USA (2017), pp. 962 -- 970 . Zafar, M. B., Valera, I., Gomez-Rodriguez, M., and Gummadi, K. P. Fairness constraints: Mechanisms for fair classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA (2017), pp. 962--970."},{"key":"e_1_3_2_2_49_1","first-page":"228","volume-title":"Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Zafar M. B.","year":"2017","unstructured":"Zafar , M. B. , Valera , I. , Gomez-Rodriguez , M. , Gummadi , K. P. , and Weller , A . From parity to preference-based notions of fairness in classification . In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 , 4-9 December 2017 , Long Beach, CA, USA (2017), pp. 228 -- 238 . Zafar, M. B., Valera, I., Gomez-Rodriguez, M., Gummadi, K. P., and Weller, A. From parity to preference-based notions of fairness in classification. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA (2017), pp. 228--238."}],"event":{"name":"CIKM '20: The 29th ACM International Conference on Information and Knowledge Management","location":"Virtual Event Ireland","acronym":"CIKM '20","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGIR ACM Special Interest Group on Information Retrieval"]},"container-title":["Proceedings of the 29th ACM International Conference on Information & Knowledge Management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340531.3412036","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340531.3412036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:29Z","timestamp":1750197749000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340531.3412036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,19]]},"references-count":48,"alternative-id":["10.1145\/3340531.3412036","10.1145\/3340531"],"URL":"https:\/\/doi.org\/10.1145\/3340531.3412036","relation":{},"subject":[],"published":{"date-parts":[[2020,10,19]]},"assertion":[{"value":"2020-10-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}