SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2002.06742 · ICML · 2020

Individual Fairness for k-Clustering

Sepideh Mahabadi, Ali Vakilian

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We give a local search based algorithm for k-median and k-means (and more generally for any k-clustering with p norm cost function) from the perspective of individual fairness. More precisely, for a point x in a point set P of size n, let r(x) be the minimum radius such that the ball of radius r(x) centered at x has at least n/k points from P . Intuitively, if a set of k random points are chosen from P as centers, every point x ∈ P expects to have a center within radius r(x). An individually fair clustering provides such a guarantee for every point x ∈ P . This notion of fairness was introduced in [JKL19] where they showed how to get an approximately feasible k-clustering with respect to this fairness condition. In this work, we show how to get a bicriteria approximation for fair k-clustering: The k-median (k-means) cost of our solution is within a constant factor of the cost of an optimal fair k-clustering, and our solution approximately satisfies the fairness condition (also within a constant factor). Further, we complement our theoretical bounds with empirical evaluation.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2002.06742")
get_code_for_paper("2002.06742")
have("2002.06742")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2002.06742.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2002.06742.svg)](https://syntology.ai/paper/2002.06742)

Connect an agent — have() is free.