kth.sePublications KTH
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights
CISPA Helmholtz Center for Information Security Saarbrücken, Germany.
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5211-112X
Max Planck Institute for Software Systems Kaiserslautern, Germany.
2025 (English)In: WWW 2025 - Proceedings of the ACM Web Conference, Association for Computing Machinery (ACM) , 2025, p. 4458-4469Conference paper, Published paper (Refereed)
Abstract [en]

Data summarization tasks are often modeled as k-clustering problems, where the goal is to choose k data points, called cluster centers, that best represent the dataset by minimizing a clustering objective. A popular objective is to minimize the maximum distance between any data point and its nearest center, which is formalized as the k-center problem. While in some applications all data points can be chosen as centers, in the general setting, centers must be chosen from a predefined subset of points, referred as facilities or suppliers; this is known as the k-supplier problem. In this work, we focus on fair data summarization modeled as the fair k-supplier problem, where data consists of several groups, and a minimum number of centers must be selected from each group while minimizing the k-supplier objective. The groups can be disjoint or overlapping, leading to two distinct problem variants each with different computational complexity. We present 3-approximation algorithms for both variants, improving the previously known factor of 5. For disjoint groups, our algorithm runs in polynomial time, while for overlapping groups, we present a fixed-parameter tractable algorithm, where the exponential runtime depends only on the number of groups and centers. We show that these approximation factors match the theoretical lower bounds, assuming standard complexity theory conjectures. Finally, using an open-source implementation, we demonstrate the scalability of our algorithms on large synthetic datasets and assess the price of fairness on real-world data, comparing solution quality with and without fairness constraints.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM) , 2025. p. 4458-4469
Keywords [en]
Algorithmic bias, Algorithmic fairness, Fair clustering, Fair k-center, Fair k-supplier, Responsible computing
National Category
Computer Sciences Computer graphics and computer vision
Identifiers
URN: urn:nbn:se:kth:diva-363997DOI: 10.1145/3696410.3714857ISI: 001505285200370Scopus ID: 2-s2.0-105005145530OAI: oai:DiVA.org:kth-363997DiVA, id: diva2:1962833
Conference
34th ACM Web Conference, WWW 2025, Sydney, Australia, April 28 - May 2, 2025
Note

Part of ISBN 9798400712746

QC 20250603

Available from: 2025-06-02 Created: 2025-06-02 Last updated: 2025-12-08Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Gionis, Aristides

Search in DiVA

By author/editor
Gionis, Aristides
By organisation
Theoretical Computer Science, TCS
Computer SciencesComputer graphics and computer vision

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 133 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf