2024-04-18-bateni24a.md

title	software	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
A Scalable Algorithm for Individually Fair k-Means Clustering	https://github.com/google-research/google-research/tree/master/individually_fair_clustering/	We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. Given $n$ points $P$ in a metric space, let $\delta(x)$ for $x\in P$ be the radius of the smallest ball around $x$ containing at least $n / k$ points. A clustering is then called individually fair if it has centers within distance $\delta(x)$ of $x$ for each $x\in P$. While good approximation algorithms are known for this problem no efficient practical algorithms with good theoretical guarantees have been presented. We design the first fast local-search algorithm that runs in  $O(nk^2)$ time and obtains a bicriteria $(O(1), 6)$ approximation. Then we show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	bateni24a	0	A Scalable Algorithm for Individually Fair k-Means Clustering	3151	3159	3151-3159	3151	false	Bateni, MohammadHossein and Cohen-Addad, Vincent and Epasto, Alessandro and Lattanzi, Silvio	given family MohammadHossein Bateni given family Vincent Cohen-Addad given family Alessandro Epasto given family Silvio Lattanzi	2024-04-18		Proceedings of The 27th International Conference on Artificial Intelligence and Statistics	238	inproceedings	date-parts 2024 4 18	https://proceedings.mlr.press/v238/bateni24a/bateni24a.pdf