Approximating Fair $k$-Min-Sum-Radii in $\mathbb{R}^d$
- URL: http://arxiv.org/abs/2309.00834v1
- Date: Sat, 2 Sep 2023 06:01:59 GMT
- Title: Approximating Fair $k$-Min-Sum-Radii in $\mathbb{R}^d$
- Authors: Lukas Drexler, Annika Hennes, Abhiruk Lahiri, Melanie Schmidt, Julian
Wargalla
- Abstract summary: We study the $k$-min-sum-radii problem in Euclidean spaces of arbitrary dimension for the case of constant $k$.
We propose a PTAS for the fair $k$-min-sum-radii problem in Euclidean spaces of arbitrary dimension for the case of constant $k$.
- Score: 1.7561849652813544
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The $k$-center problem is a classical clustering problem in which one is
asked to find a partitioning of a point set $P$ into $k$ clusters such that the
maximum radius of any cluster is minimized. It is well-studied. But what if we
add up the radii of the clusters instead of only considering the cluster with
maximum radius? This natural variant is called the $k$-min-sum-radii problem.
It has become the subject of more and more interest in recent years, inspiring
the development of approximation algorithms for the $k$-min-sum-radii problem
in its plain version as well as in constrained settings.
We study the problem for Euclidean spaces $\mathbb{R}^d$ of arbitrary
dimension but assume the number $k$ of clusters to be constant. In this case, a
PTAS for the problem is known (see Bandyapadhyay, Lochet and Saurabh, SoCG,
2023). Our aim is to extend the knowledge base for $k$-min-sum-radii to the
domain of fair clustering. We study several group fairness constraints, such as
the one introduced by Chierichetti et al. (NeurIPS, 2017). In this model, input
points have an additional attribute (e.g., colors such as red and blue), and
clusters have to preserve the ratio between different attribute values (e.g.,
have the same fraction of red and blue points as the ground set). Different
variants of this general idea have been studied in the literature. To the best
of our knowledge, no approximative results for the fair $k$-min-sum-radii
problem are known, despite the immense amount of work on the related fair
$k$-center problem.
We propose a PTAS for the fair $k$-min-sum-radii problem in Euclidean spaces
of arbitrary dimension for the case of constant $k$. To the best of our
knowledge, this is the first PTAS for the problem. It works for different
notions of group fairness.
Related papers
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al.
A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$.
We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z) - A Unified Framework for Gradient-based Clustering of Distributed Data [51.904327888475606]
We develop a family of distributed clustering algorithms that work over networks of users.
DGC-$mathcalF_rho$ is specialized to popular clustering losses like $K$-means and Huber loss.
We show that consensus fixed points of DGC-$mathcalF_rho$ are equivalent to fixed points of gradient clustering over the full data.
arXiv Detail & Related papers (2024-02-02T10:44:42Z) - Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
We consider the problem of latent bandits with cluster structure where there are multiple users, each with an associated multi-armed bandit problem.
We propose LATTICE which allows exploitation of the latent cluster structure to provide the minimax optimal regret of $widetildeO(sqrt(mathsfM+mathsfN)mathsfT.
arXiv Detail & Related papers (2023-01-17T17:49:04Z) - Improved Approximation Algorithms for Individually Fair Clustering [9.914246432182873]
We present an improved $(16p +varepsilon,3)$-bicriteria approximation for the fair $k$-clustering with $ell_p$-norm cost.
Our approach suggests a reduction from our individually fair clustering to a clustering with a group fairness requirement proposed by Kleindessner et al.
arXiv Detail & Related papers (2021-06-26T15:22:52Z) - A New Notion of Individually Fair Clustering: $\alpha$-Equitable
$k$-Center [31.936733991407134]
We introduce a novel definition of fairness for clustering problems.
In our model each point $j$ has a set of other points $mathcalS_j$ that it perceives as similar to itself.
We provide efficient and easily implementable approximation algorithms for the $k$-center objective.
arXiv Detail & Related papers (2021-06-09T22:52:00Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem.
We show that by making few queries, the problem becomes easier to solve.
arXiv Detail & Related papers (2021-06-04T02:32:26Z) - Revisiting Priority $k$-Center: Fairness and Outliers [5.3898004059026325]
We develop a framework that yields constant factor approximation algorithms for Priority $k$-Center with outliers.
Our framework extends to generalizations of Priority $k$-Center to matroid and knapsack constraints.
arXiv Detail & Related papers (2021-03-04T21:15:37Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints.
For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
arXiv Detail & Related papers (2021-01-20T04:29:18Z) - KFC: A Scalable Approximation Algorithm for $k$-center Fair Clustering [6.09170287691728]
We study the problem of fair clustering on the $k-$center objective.
In fair clustering, the input is $N$ points, each belonging to at least one of $l$ protected groups.
Our algorithm is effective in finding good clusters without over-representation or under-representation.
arXiv Detail & Related papers (2020-10-26T23:33:34Z) - Computationally efficient sparse clustering [67.95910835079825]
We provide a finite sample analysis of a new clustering algorithm based on PCA.
We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
arXiv Detail & Related papers (2020-05-21T17:51:30Z) - Structures of Spurious Local Minima in $k$-means [20.155509538529568]
We investigate the structures of spurious local solutions to the $k$-means problem.
We prove that this is essentially the only type of spurious local minima under a separation condition.
arXiv Detail & Related papers (2020-02-16T22:15:03Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.