Aarhus University Seal

Fair Coresets and Streaming Algorithms for Fair k-means

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

We study fair clustering problems as proposed by Chierichetti et al. [CKLV17]. Here, points have a sensitive attribute and all clusters in the solution are required to be balanced with respect to it (to counteract any form of data-inherent bias). Previous algorithms for fair clustering do not scale well. We show how to model and compute so-called coresets for fair clustering problems, which can be used to significantly reduce the input data size. We prove that the coresets are composable [IMMM14] and show how to compute them in a streaming setting. This yields a streaming PTAS for fair k-means in the case of two colors (and exact balances). Furthermore, we extend techniques due to Chierichetti et al. [CKLV17] to obtain an approximation algorithm for k-means, which leads to a constant factor algorithm in the streaming model when combined with the coreset.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 17th International Workshop, WAOA 2019, Revised Selected Papers
EditorsEvripidis Bampis, Nicole Megow
Number of pages20
Publication year2020
ISBN (print)9783030394783
Publication statusPublished - 2020
Externally publishedYes
Event17th International Workshop on Approximation and Online Algorithms, WAOA 2019 - Munich, Germany
Duration: 12 Sept 201913 Sept 2019


Conference17th International Workshop on Approximation and Online Algorithms, WAOA 2019
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11926 LNCS

Bibliographical note

Funding Information:
This work was done while the first author was at University of Bonn and the third author was at TU Dortmund. The second author acknowledges support by the ERC Advanced Grant 788893 AMDROMA.

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

Copyright 2020 Elsevier B.V., All rights reserved.

See relations at Aarhus University Citationformats

ID: 207579045