Improved Approximation Algorithms for Individually Fair Clustering

28. Březen 2022

Řečníci

O prezentaci

We consider the k-clustering problem with ℓ_p-norm cost, which includes k-median, k-means and k-center cost functions, under an individual notion of fairness proposed by Jung et al. [2020]: given a set of points P of size n, a set of k centers induces a fair clustering if for every point v∈ P, v can find a center among its n/k closest neighbors. Recently, Mahabadi and Vakilian [2020] showed how to get a ( p^O(p),7)-bicriteria approximation for the problem of fair k-clustering with ℓ_p-norm cost: every point finds a center within distance at most 7 times its distance to its (n/k)-th closest neighbor and the ℓ_p-norm cost of the solution is at most p^O(p) times the cost of an optimal fair solution.In this work, for any >0, we present an improved (16^p +,3)-bicriteria approximation for the fair k-clustering with ℓ_p-norm cost. To achieve our guarantees, we extend the framework of [Charikar et al.,2002, Swamy, 2016] and devise a 16^p-approximation algorithm for the facility location with ℓ_p-norm cost under matroid constraint which might be of an independent interest. Besides, our approach suggests a reduction from our individually fair clustering to a clustering with a group fairness requirement proposed by Kleindessner et al. [2019, which is essentially the median matroid problem.

Organizátor

O organizátorovi (AISTATS 2022)

AISTATS is an interdisciplinary gathering of researchers at the intersection of computer science, artificial intelligence, machine learning, statistics, and related areas. Since its inception in 1985, the primary goal of AISTATS has been to broaden research in these fields by promoting the exchange of ideas among them. We encourage the submission of all papers which are in keeping with this objective at AISTATS.

Uložení prezentace

Měla by být tato prezentace uložena po dobu 1000 let?

Jak ukládáme prezentace

Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %

Sdílení

Doporučená videa

Prezentace na podobné téma, kategorii nebo přednášejícího

Zajímají Vás podobná videa? Sledujte AISTATS 2022