A Subquadratic Time Approximation Algorithm for Individually Fair k-Center

Matthijs Ebbens, Nicole Funk, Jan Höckendorff, Christian Sohler, Vera Weil · 2024

Read A Subquadratic Time Approximation Algorithm for Individually Fair k-Center by Matthijs Ebbens, Nicole Funk, Jan Höckendorff, Christian Sohler, Vera Weil (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04943.txt.

Introduction

Matthijs Ebbens and co-authors give in 2024 faster approximation methods for fair k-center clustering. Each point earns a fairness radius from its near neighbors' distance. A valid clustering keeps a center inside each point's radius while it holds total cost low.

One exact method runs in near quadratic time with both factors at two. A sampled random method runs far faster with a looser distance factor. The sampling trick grades all fairness radii in well under quadratic time. That trick may serve fair clustering work beyond this problem. Both methods carry twofold bounds on distance stretch and total cost.

Catalog record

CREATORMatthijs Ebbens, Nicole Funk, Jan Höckendorff, Christian Sohler, Vera Weil
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-04943

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center Matthijs Ebbens, Nicole Funk, Jan Höckendorff, Christian Sohler, Vera Weil Abstract 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 (\beta,\gamma) -approximation algorithms that compute clusterings such that every point x\in P has a center within distance \beta r_{x} and the clustering cost is at most \gamma 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/\delta)+k^{2}/\varepsilon) time (10,2+\varepsilon) -approximation algorithm, where \delta 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. 1 INTRODUCTION Clustering is the process of partitioning a given data set into subsets such that, ideally, the elements in each subset are similar to each other and elements in different subsets are less similar. It is a basic approach in unsupervised learning with applications in, for example, signal processing [ 1 ] , community detection in networks [ 2 ] [ 3 ] , outlier detection [ 4 ] and data summarization [ 5 ] . For many clustering problems each cluster has a corresponding center that can be viewed as a representative of all points contained in the given cluster. Data points closer to the center are naturally better represented than those that are far away. Ideally, we would like every data point to be close to its representative center, but this is usually impossible to realize. One way to mitigate this is to use clustering objectives such as k -median or k -means clustering that optimize the average (squared) distance to the cluster center. But optimizing the average distance will often lead to some data points being less well represented than they could be. In applications where data points model humans, such a behaviour may be undesirable and raises the question how to obtain a clustering that is acceptable for everyone. This problem is addressed in a recent paper by Jung et al. [ 6 ] that introduced the notion of individual fairness in the context of clustering. Individual fairness can be thought of as a clustering constraint that ensures that every data point is assigned to a center that is not much worse than what one could hope for in a certain average-type setting: If one partitions a data set with n points in k clusters then on average a cluster has n/k data points [ 6 ] . Thus, individual fairness is defined to be the constraint that every data point has a center among its \lceil n/k\rceil -th nearest neighbors. Individually fair clustering was mainly studied for k -median and k -means clustering in metric spaces and generalizations to l_{p} -norm type distance functions [ 7 ] [ 8 ] [ 9 ] [ 10 ] . This also led to results on the individually fair k -center problem, which we will call the \alpha -fair k -center problem. In this paper, we show that the properties of the \alpha -fair k -center problem can be exploited to achieve a simple algorithm that improves upon the current state of the art. We then give another algorithm that achieves a randomized constant bicriteria approximation in O(kn\log(n/\delta)) time where \delta>0 is a parameter that bounds the failure probability. To do so, we develop a procedure to approximate the distances to the \lceil n/k\rceil -th nearest neighbors of each data point in that running time. We believe that this procedure may find further applications in the context of individual fairness. 2 OUR CONTRIBUTIONS In this work, we give a O(n^{2}+kn\log n) time (2,2) -bicriteria approximation algorithm for the individually \alpha -fair metric k -center problem, improving upon the current state of the art (3,3) -approximation algorithm by Vakilian and Yalçiner [ 9 ] . Result 1 (Simplified restatement of Theorem 8 ) . Algorithm (2,2) -ApproxFairCenter is a (2,2) -bicriteria approximation algorithm for the individually \alpha -fair (discrete) metric k -center problem with O(n^{2}+kn\log n) running time, where n is the number of input points. As the running time of this algorithm is dominated by the computation of the \lceil n/k\rceil -th nearest neighbors of each data point, we develop a randomized approximation algorithm for these distances under the assumption that k is smaller than n/6 (if this is not the case we can compute all distances to the \lceil n/k\rceil -th nearest neighbors exactly in O(nk) time). Result 2 (Simplified restatement of Lemma 11 ) . Let (P,d) be a finite metric space. Algorithm ApproxFairRadii computes with probability at least 1-\delta for all p\in P a 5 -approximation to the distance of the \lceil n/k\rceil -th nearest neighbor. The running time of the algorithm is O(nk\log(n/\delta)) . Using the approximated distances, we modify the (2,2) -approximation algorithm to obtain a randomized approximation algorithm with subquadratic running time if k is asymptotically smaller than n . Result 3 (Simplified restatement of Theorem 13 ) . Let \delta,\varepsilon>0 . Algorithm (10,2+\epsilon) -ApproxFairCenter is a randomized algorithm that computes with probability at least 1-\delta a (10,2+\epsilon) -bicriteria approximation for the individually \alpha -fair (discrete) metric k -center problem. The running time of the algorithm is O(nk(\log(n/\delta))+k^{2}/\varepsilon) , where n is the number of input points. 3 RELATED WORK For the k -center problem there is a O(nk) time 2 -approximation by Gonzalez [ 11 ] and it is known that the problem is NP-complete to approximate with a factor less than 2 [ 12 ] . The notion of individual fairness we consider in this paper was introduced by Jung et al. [ 6 ] for k -clustering in general, but also studied previously in other contexts such as priority clustering [ 13 ] and metric embedding [ 14 ] [ 15 ] . In fact, individually fair clustering is a special case of priority clustering [ 16 ] . In the context of individual fairness, a clustering of size k is \alpha -fair for a set of points P and some \alpha>0 if for each point p in P there is a center within \alpha times the distance to its \lceil|P|/k\rceil -th nearest neighbor in P . Jung et al. [ 6 ] showed that solving k -clustering under individual fairness with \alpha=1 is NP-hard in any metric space. They additionally designed an algorithm that computes a k -center clustering that is 2 -fair but lacks any guarantee on the cost. In the context of individually fair k -clustering, previous work studied algorithms for arbitrary \ell_{p} norm cost functions including k -center, k -median and k -means as special cases [ 7 ] [ 8 ] [ 9 ] [ 10 ] . We start by stating the results for the case of

Read the complete text