A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912292092772352 |
|---|---|
| author | Ebbens, Matthijs Funk, Nicole Höckendorff, Jan Sohler, Christian Weil, Vera |
| author_facet | Ebbens, Matthijs Funk, Nicole Höckendorff, Jan Sohler, Christian Weil, Vera |
| contents | We study the $k$-center problem in the context of individual fairness. Let $P$ be a set of $n$ points in a metric space and $r_x$ be the distance between $x \in P$ and its $\lceil n/k \rceil$-th nearest neighbor. The problem asks to optimize the $k$-center objective under the constraint that, for every point $x$, there is a center within distance $r_x$. We give bicriteria $(β,γ)$-approximation algorithms that compute clusterings such that every point $x \in P$ has a center within distance $βr_x$ and the clustering cost is at most $γ$ times the optimal cost. Our main contributions are a deterministic $O(n^2+ kn \log n)$ time $(2,2)$-approximation algorithm and a randomized $O(nk\log(n/δ)+k^2/\varepsilon)$ time $(10,2+\varepsilon)$-approximation algorithm, where $δ$ denotes the failure probability. For the latter, we develop a randomized sampling procedure to compute constant factor approximations for the values $r_x$ for all $x\in P$ in subquadratic time; we believe this procedure to be of independent interest within the context of individual fairness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04943 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Subquadratic Time Approximation Algorithm for Individually Fair k-Center Ebbens, Matthijs Funk, Nicole Höckendorff, Jan Sohler, Christian Weil, Vera Data Structures and Algorithms Computational Geometry We study the $k$-center problem in the context of individual fairness. Let $P$ be a set of $n$ points in a metric space and $r_x$ be the distance between $x \in P$ and its $\lceil n/k \rceil$-th nearest neighbor. The problem asks to optimize the $k$-center objective under the constraint that, for every point $x$, there is a center within distance $r_x$. We give bicriteria $(β,γ)$-approximation algorithms that compute clusterings such that every point $x \in P$ has a center within distance $βr_x$ and the clustering cost is at most $γ$ times the optimal cost. Our main contributions are a deterministic $O(n^2+ kn \log n)$ time $(2,2)$-approximation algorithm and a randomized $O(nk\log(n/δ)+k^2/\varepsilon)$ time $(10,2+\varepsilon)$-approximation algorithm, where $δ$ denotes the failure probability. For the latter, we develop a randomized sampling procedure to compute constant factor approximations for the values $r_x$ for all $x\in P$ in subquadratic time; we believe this procedure to be of independent interest within the context of individual fairness. |
| title | A Subquadratic Time Approximation Algorithm for Individually Fair k-Center |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2412.04943 |