Data summarization is a central problem in the area of machine learning, where we want to compute a small summary of the data. For example, if the input data is enormous, we do not want to run our machine learning algorithm on the whole input but on a small representative subset. How we select such a representative summary is quite important. It is well known that if the input is biased, then the machine learning algorithms trained on this data will exhibit the same bias. This is a classic example of selection bias but as exhibited by algorithms themselves. Currently used algorithms for data summarization have been shown to be biased with respect to attributes such as gender, race, and age (see, e.g., [KMM15]), and this motivates the fair data summarization problem. Recently, the fair k-center problem was shown to be useful in computing fair summary [KAM19]. In this paper, we continue the study of fair k-center and add to the series of works on fairness in machine learning algorithms. Our main results are streaming and distributed algorithms for fair k-center. These models are extremely suitable for handling massive datasets. The fact that data summarization problem arises when the input is huge makes our work all the more relevant!

Suppose the input is a set of real vectors with a gender attribute and you want to compute a summary of k data points such that both1 genders are represented equally. Say we are given a summary S. The cost we pay for not including a point in S is its Euclidean distance from S. Then the cost of S is the largest cost of a point. We want to compute a summary with minimum cost that is also fair, i.e., contains k/2 women and k/2 men. In one sentence, we want to compute a fair summary such that the point that is farthest from this summary is not too far. Fair k-center models this task: let the number of points in the input be n, the number of groups be m, target summary size be k, and we want to select a summary points belonging to Group . And we want to minimize denotes the distance function. Note that each point belongs to exactly one of the m groups; for the case of gender, m = 2.

We call the special case where -center throughout this paper. For k-center, there are simple greedy algorithms with an approximation ratio of 2 [Gon85, HS85], and getting better than 2-approximation is NP-hard [HN79]. The NP-hardness result also applies to the more general fair k-center. The best algorithm known for fair k-center is a 3-approximation algorithm that runs in time ]. A linear-time algorithm with approximation guarantee of , which is constant if m is, was given recently [KAM19]. Both of these algorithms work only in the traditional random access machine model, which is suitable only if the input is small enough to ft into fast memory. We give a two-pass streaming algorithm that achieves the approximation ratio arbitrarily close to 3. In the streaming setting, input is thought to arrive one point at a time, and the algorithm has to process the input quickly, using minimum amount of working memory—ideally linear in the size of a feasible solution, which is k for fair k-center. Our algorithm processes each incoming input point in O(k) time and uses space O(km), which is O(k) if the number of groups m is very small. This improves the space usage of the existing streaming algorithm [Kal19] almost quadratically, from , while also matching the best approximation ratio achieved by Chen et al. We also give the frst distributed, constant approximation algorithm where the input is divided among multiple processors, each of which performs one round of computation and sends a message of size O(km) to a central processor, which then computes the fnal solution. Both rounds of computation are linear time. All the approximation, communication, space usage, and running-time guarantees are provable. To complement our distributed algorithm, we prove that any distributed algorithm, even randomized, that works by each processor sending a subset of its input to a central processor which outputs the solution, needs to essentially communicate the whole input to achieve an approximation ratio of better than 4. This, in fact, applies for the special case of k-center showing that known 4-approximation algorithm [MKC-center is optimal.

We perform experiments on real and synthetic datasets and show that our algorithms are as fast as the linear-time algorithm of Kleindessner et al., while achieving improved approximation ratio, which matches that of Chen et al. Note that this comparison is possible only for small datasets, since those algorithms do not work either in streaming or in distributed setting. We also run our algorithms on a really large synthetic dataset of size 100GB, and show that their running time is only one order of magnitude more than the time taken to just read the input dataset from secondary memory.

As a further contribution, we give faster implementations of existing algorithms—those of Kale and Chen et al.

Related work

Chen et al. gave the frst polynomial-time algorithm that achieves 3-approximation. Kale achieves almost the same ratio using just two passes and also gives a one-pass -approximation algorithm, both using

One way that is incomparable to ours is to compute a fair summary is using a determinantal measure of diversity [CKS]. Fair clustering has been studied under another notion of fairness, where each cluster must be balanced with respect to all the groups (no over-or-under-representation of any group) [CKLV17], and this line of work also has received a lot of attention in a short span of time [BCFN19, AEKM19, BIPV19, SSS20, JSS20].

The k-median clustering problem with fairness constraints was frst considered by [HKK10] and with more general matroid constraints was studied by [KKN]. The work of Chen et al. and Kale also actually

applies for matroid constraints. There has been a lot of work done on fairness, and we refer the reader to overviews by [KAM19,

The input to fair k-center is a set X of n points in a metric space given by a distance function d. We denote this metric space by (X,d). Each point belongs to one of m groups, say denote this group assignment function. Further, for each group j, we are given a capacity . We call a subset if for every j, the set S contains at most points from group j. The goal is to compute a feasible set of centers that (approximately) minimizes the clustering cost, formally defned as follows.

, then the clustering cost of A for B is defned as

Note here that we allow A to not be a subset of B. The following lemmas follow easily from the fact that the distance function d satisfes the triangle inequality.

. The clustering cost of A for C is at most the clustering cost of A for B plus the clustering cost of B for C.

Lemma 2. Suppose for a set T of points there exists a set S of k centers, not necessarily a subset of T , whose clustering cost for T is at most is a set of points separated pairwise by distance more than

Proof. If |P| > k then some two points in P must share one of the k centers, and must therefore be both within distance from that common center. Then by the triangle inequality, they cannot be separated by distance more than

We denote by a feasible set which has the minimum clustering cost for X, and by OPT the minimum clustering cost. We assume that our algorithms have access to an estimate of OPT. When is at least OPT, our algorithms compute a solution of cost at most for a constant . Thus, when our algorithms compute a -approximate solution. In Section 3.3 we describe how to efciently compute such a

Before stating algorithms, we describe some elementary procedures which will be used as subroutines in our algorithms.

takes as input a set T of points with distance function d and a radius r. Starting with , it performs a single pass over T. Whenever it fnds a point q which is not within distance r from any point in P, it adds q to P. Finally, it returns P. Thus, P is a maximal subset of T of points separated pairwise by distance more than r. We call points in P pivots. By Lemma 2, if there is a set of k points whose clustering cost for T is at most . Moreover, due to maximality of P, its clustering cost for T is at most r. Note that runs in time

takes as input a set T of points with distance function d, a group assignment function , and a radius , initializing N(p) = {p}, it includes in N(p) one point, from each group, which is within distance r from p whenever such a point exists. Note that this is done while performing a single pass over T. This procedure runs in time

Informally, if P is a good but infeasible set of centers, then fnds representatives N(p) of the groups in the vicinity of each . This, while increasing the clustering cost by at most r, gives us enough fexibility to construct a feasible set of centers. The procedure that we describe next fnds a feasible set from a collection of sets of representatives.

a group assignment function g, and a vector of capacities of the m groups. It returns a feasible set S intersecting as many ’s as possible. This reduces to fnding a maximum cardinality matching in an appropriately constructed bipartite graph. It is important to note that this procedure does the post-processing: it doesn’t make any pass over the input stream of points. This procedure runs in time

For interested readers, the pseudocodes of these procedures, an explanation of proof of its running time appear in Appendix A.

3.1 A Two-Pass Algorithm

Recall that is an upper bound on the minimum clustering cost. Our two-pass algorithm given by Algorithm 1 consists of three steps. First, the algorithm constructs a maximal subset of pivots separated pairwise by distance more than by executing one pass on the stream of points. In another pass, the algorithm computes a representative set N(q) of each pivot . Points in the representative set of a pivot are within distance from the pivot. Due to the separation of between the pivots, these representative sets are pairwise disjoint. Finally, a feasible set S intersecting as many N(q)’s as possible is found and returned. (It will soon be clear that S intersects all the

The algorithm needs working space only to store the pivots and their representative sets. By substituting , the number of pivots is at most contains at most one point from any group, it has at most points other than q. Thus,

Observation 1. The two-pass algorithm needs just enough working space to store km points.

The calls to both take time time per point. The call to takes time

Observation 2. The two-pass algorithm runs in time , the number of groups, is constant.

We now prove the approximation guarantee.

Theorem 1. The two-pass algorithm returns a feasible set whose clustering cost is at most . This is a -approximation when

Proof. Recall that is a feasible set having clustering cost at most a point such that . Since the points in P are separated by distance more than , the points are all distinct. Recall that N(q), the output of , contains one point from every group which has a point within distance . Therefore, N(q) contains a point, say , from the same group as such that . Consider the set . This set intersects N(q) for each q. Furthermore, B contains exactly as many points from any group as , and therefore, B is feasible. Thus, there exists a feasible set, namely B, intersecting all the pairwise disjoint N(q)’s. Recall that S, the output of , is a feasible set intersecting as many N(q)’s as possible. Thus, S also intersects all the

Now, the clustering cost of S for P is at most intersects . The clustering cost of P for X is at most by the maximality of the set returned by . These facts and Lemma 1 together imply that the clustering cost of S, the output of the algorithm, for X is at most

3.2 A Distributed Algorithm

In the distributed model of computation, the set X of points to be clustered is distributed equally among processors. Each processor is allowed a restricted access to the metric d: it may compute the distance between only its own points. Each processor performs some computation on its set of points and sends a summary of small size to a coordinator. From the summaries, the coordinator then computes a feasible set S of points which covers all the n points in X within a small radius. Let denote the set of points distributed to processor i.

The algorithm executed by each processor i is given by Algorithm 2, which consists of two main steps. In the frst step, the processor uses Gonzalez’s farthest point heuristic to fnd k + 1 points. The frst k of those constitute the set , which we will call the set of local pivots. The point is the farthest point from the set of local pivots, and it is at a distance from the set of local pivots. Thus, every point within distance from the set of pivots. This means,

Observation 3. The clustering cost of

In the second step, for each local pivot , the processor computes a set L(p) of local representatives in the vicinity of p. Finally, the set of local pivots and the union of local representative sets is sent to the coordinator. Since L(p) contains at most one point from any group, it has at most points other than we have the following observation.

Observation 4. Each processor sends at most km points to the coordinator.

Moreover, the separation between the local pivots is bounded as follows.

Lemma 3. For every processor

is a set of k +1 points separated pairwise by distance more than is a set of at most k points whose clustering cost for . This contradicts Lemma 2.

Observation 3 allows us to defne a covering function cov from X, the input set of points, to the set of local pivots, as follows.

Defnition 2. Let p be an arbitrary point in X. Suppose p is processed by processor cov(p) is an arbitrary local pivot in within distance

Since the processors send only a small number of points to the coordinator, it is very well possible that the optimal set of centers is lost in this process. In the next lemma, we claim that the set of points received by the coordinator contains a good and feasible set of centers nevertheless.

contains a feasible set, say B, whose clustering cost for is at most

Proof. Consider any , and suppose it is processed by processor nition 2. Recall that L(cov(c)), the output of , contains one point from every group which has a point within distance . Therefore, contains some point, say same group as c (possibly c itself), such that by the triangle inequality and Lemma 3. Let has exactly as many points from any group as is feasible. The clustering cost of . The clustering cost of for is at most , the clustering cost of is at most , as required.

The algorithm executed by the coordinator is given by Algorithm 3. The coordinator constructs a maximal subset P of the set of pivots returned by the processors such that points in P are pairwise separated by distance more than is called the set of global pivots. For each global pivot , the coordinator computes a set of its global representatives, all of which are within distance . Due to the separation between points in P, the sets N(q) are pairwise disjoint. Finally, a feasible set S intersecting as many N(q)’s as possible is found and returned. (As before, it will be clear that S intersects all the

Theorem 2. The coordinator returns a feasible set whose clustering cost is at most . This is a approximation when

Proof. By Lemma 4, L contains a feasible set, say B, whose clustering cost for denote a point in B that is within distance . Since the points in separated pairwise by distance more than ’s are all distinct. By the property of N(q) returned by it contains a point, say , from the same group as are from the same group and ’s are all distinct, contains at most as many points from any group as B does. Since B is feasible, so is . To summarize, there exists a feasible set, namely , intersecting all the N(q)’s. Recall that S, the output of is a feasible set intersecting as many N(q)’s as possible. Thus, S also intersects all the

Now, the clustering cost of S for P is at most intersects clustering cost of by the maximality of the set returned by clustering cost of because the clustering cost of each at most . These facts and Lemma 1 together imply that the clustering cost of S, the output of the coordinator, for X is at most

We note here that even though our distributed algorithm has the same approximation guarantee as Kale’s one-pass algorithm, it is inherently a diferent algorithm. Ours is extremely parallel whereas Kale’s is extremely sequential. We now prove a bound on the running time.

Theorem 3. The running time of the distributed algorithm is . By an appropriate choice of , the number of processors, this can be made

Proof. For each processor i, computing local pivots as well as the call to time each. For the coordinator, the separation between the global pivots and Lemma 2 together enforce . Observation 4 implies . Therefore, takes time takes time . The call to time , thus limiting the coordinator’s running time to minimizes the total running time to

3.3 Handling the Guesses

Given an arbitrarily small parameter , a lower bound , and an upper bound our algorithms for guess , which means at most guesses. Call this method of guesses as geometric guessing starting at algorithms will compute a solution successfully.

In the distributed algorithm, by Lemma 3, for each processor, . Therefore, We then run Algorithm 3 with geometric guessing starting at until it successfully fnds a solution.

For the two-pass algorithm, let P be the set of frst k + 1 points; then lower bound (call this the simple lower bound). Note that no passes need to be spent to compute the simple lower bound. We also need an upper bound . One can compute an arbitrary solution and its cost—which will be an upper bound—by spending two more passes (call this the simple upper bound). This results in a four-pass algorithm. To obtain a truly two pass algorithm and space usage one can use Guha’s trick [Guh09], which is essentially starting guesses and if a run with guess fails, then continuing the run with guess and treating the old summary as the initial stream for this guess; see also [Kal19] for details. But obtaining and using an upper bound is convenient and easy to implement in practice.

Malkomes et al. [MKC] generalized the greedy algorithm [Gon85] to obtain a 4-approximation algorithm for the k-center problem in the distributed setting. Here we prove a lower bound for the 3-center problem with 9 processors for a special class of distributed algorithms: If each processor communicates less than a constant fraction of their input points, then with a constant probability, the output of the co- ordinator will be no better than a 4-approximation to the optimum. Figure 1 shows a graph metric with

Figure 1: The underlying metric for

points for which lower bound holds, where the point x is not a part of the metric but is only used to defne the distances. Note that is at distance of 1 from each point in

For denote an arbitrary equipartition of . There are 9 processors, whose inputs are given by goal is to solve the 3-center problem on the union of their inputs. (Observe that the optimum solution is with distance 1.) Each processor is allowed to send a subset of their input points to the coordinator, who outputs three of the received points. For this class of algorithms, we show that if each processor communicates less than points, then the output of the coordinator is no better than a 4-approximation to the optimum with probability at least 1/84. Using standard amplifcation arguments, we can generate a metric instance for the ()-center problem on which with probability at least algorithm outputs no better than 4-approximation (

We frst discuss the intuition behind the proof. The key observation is that all points in each pairwise equidistant. Therefore, sending a uniformly random subset of the inputs is the best strategy for each processor. Since each processor communicates only a small fraction of its input points, the probability that the coordinator receives any of the points in is negligible. Conditioned on the coordinator not receiving these points, all the received points are a subset of . As all points in are pairwise equidistant, the best strategy for the coordinator is to output 3 points at random. Hence, with constant probability, all the points in the output belong to or all of them belong to being the case, the output has cost 4, whereas the optimum cost is 1.

4.1 The Formal Proof

We now present the formal details of the lower bound. For a natural number n, [n] denotes the set {1,2,...,n}.

The point set of this metric space on points is given by

where . We call the points in C critical. Note that are pairwise disjoint and are also disjoint from C. The metric is the shortest-path-length metric induced by the graph shown in Figure 1 (where x is not a point in S but is only used to defne the pairwise distances). The pairwise distances are given in Table 1. Note that if the table entry i,j is indexed by sets, then the entry corresponds to the distance between distinct points in the sets. The following observation can be verifed by a case-by-case analysis.

are the only optimum solutions of the 3-center problem on and they have unit clustering cost. The clustering cost of any subset of due to point c. Similarly, the clustering cost of any subset of due to point a.

Table 1: Pairwise Distances

be an arbitrary equi- partition of (and therefore, ). Defne the sets and . Observe that each contains exactly points separated pairwise by distance 2, and moreover, three of the points are critical. We assign the sets randomly to the nine processors after a random relabeling. Formally, we pick a uniformly random bijection as the relabeling and another uniformly random bijection , independent of assignment. We assign the set to processor . When a processor or the coordinator queries the distance between as an answer. Note that neither the processors nor the coordinator knows . Let the random variable the partition of the set of labels into a sequence of nine subsets induced by is the set of labels of points assigned to processor

Lemma 5. Consider any deterministic distributed algorithm for the 9 processor 3-center problem on and input distribution D, in which each processor communicates an -sized subset of its input points, and the coordinator outputs 3 of the received points. If , then with probability at least 1/84, the output is no better than a 4-approximation.

Although the probability with which the coordinator fails to outputs a better-than-4-approximation is only 1/84, it can be . We discuss the amplifcation result before presenting the proof of the above lemma.

be arbitrary constants, and let

Then there exists an instance of the -center problem such that, in the distributed setting with 9 processors, each communicating at most a c fraction of its input points to the coordinator, the coordinator fails to output a better than 4-approximation with probability at least

Proof. The underlying metric space consists of disjoint copies of separated by an arbitrarily large distance from one another. The point set of each copy is distributed to the nine processors as described earlier, and these distribtions are independent. Thus, each processor receives points. Observation 5 implies that in this instance, the optimum set of centers (the union of optimum sets of 3 centers in each copy) has unit cost. Also, in order to get a better than 4-approximation, the coordinator must output a better than 4-approximate solution from every copy. We prove that this is unlikely.

By our assumption, each processor sends at most points to the coordinator, where c < 1/486. Therefore, for each processor, there exist at most copies from which it sends more than points to the coordinator. Since we have 9 processors, there exist at most copies from which more than points are sent by some processor. From each of the remaining copies, no processor sends more than points. By Lemma 5, the coordinator succeeds on each of these copies independently with probability at most , in producing a better than 4 approximation. Therefore, the probability that the coordinator succeeds in all the copies is bounded as

where the last inequality follows by substituting the value of . Thus, the coordinator fails to produce a better than 4-approximation with probability at least

Proof of Lemma 5. Consider any one of the nine processors. It gets the set for a uniformly random is a uniformly random labeling and points in are pairwise equidistant, the processor is not able to identify the three critical points in its input. This happens even if we condition on the values of . Formally, conditioned on , all subsets of are equally likely to be the set of labels of the three critical points in processor r’s input, i.e., consequence, the probability that at least one of the three critical points appears in the set of at most points the processor communicates is at most , even when we condition on given processor be the set of labels it sends to the coordinator, and defne to be the event that contains the label of a critical point. Then . Next, defne G to be the event that no processor sends the label of any critical point to the coordinator, that is, is the complement of . Then by the union bound and the fact that , we have for every partition P of the label set and every bijection

Suppose the coordinator outputs O, a set of three labels, on receiving . Observe that are all completely determined2 by P. In contrast, due to the random labeling , the mapping is independent of P. Therefore,

Observation 6. Conditioned on P, the bijection is equally likely to be any of the 9! bijections from to [9].

Next, defne to be the event that In words, is the event that the coordinator outputs labels of three points, all of which are contained in . Note that the event implies that the coordinator’s output is contained in . Therefore, by Observation 5, event that the coordinator fails to output a better than 4-approximation. We are now left to bound from below.

Since the set is completely determined by P, the event is completely determined by P and , there exist exactly which cause to happen. Formally,

Observation 7. For every partition P of the label set, there exist exactly bijections for all the other bijections

Therefore, we have,

Here, we used Observation 7 for the second and fourth equality, and Equation (1) and Observation 6 for the inequality. Thus, the coordinator fails to output a better than 4-approximation with probability at least 1/84, as required.

Using Lemma 6 along with Yao’s lemma, we get our main lower-bound theorem.

Theorem 4. There exists c > 0 such that for any , any randomized distributed algorithm for k-center where each processor communicates at most cn points to the coordinator, who outputs a subset of those points as the solution, is no better than 4-approximation with probability at least

All experiments are run on HP EliteBook 840 G6 with Intel® Core™ i7-8565U CPU 1.80GHz having 4 cores and 15.5 GiB of RAM, running Ubuntu 18.04 and Anaconda. We make our code available on GitHub3.

We perform our experiments on a massive synthetic dataset, several real datasets, and small synthetic datasets. The same implementation is used for the large synthetic dataset and the real datasets, but a slightly diferent implementation is used for small synthetic datasets. Before presenting the experiments, we frst discuss the implementation details that are common to all three experiments. Specifc details are mentioned along with the corresponding experimental setup. For all our algorithms if the solution size is less than k, then we extend the solution using an arbitrary solution of size k (which also certifes the simple upper bound). In the case of the distributed algorithm, an arbitrary solution is computed using only the points received by the coordinator. Also, one extra pass is spent into computing solution cost. In the processors’ algorithm, we return along with . No randomness is used for any optimization, making our algorithms completely deterministic. Access to distance between two points is via a method , whose implementation depends on the dataset.

We use the code shared by Kleindessner et al. for their algorithm on github4, exactly as is, for all datasets. In their code, the distance is assumed to be stored in an distance matrix.

As mentioned in the introduction, we give new implementations for existing algorithms—those of Chen et al. and Kale (we choose to implement Kale’s two-pass algorithm only, because it is the better of his two). Instead of using a matroid intersection subroutine, which can have running time of super quadratic in n, we reduce the postprocessing steps of these algorithms to fnding a maximum matching in an appropriately constructed graph (for details, see in Appendix A). We further reduce maximum matching to max-fow which is computed using Python package NetworkX. This results in a postprocessing time of for Chen et al. and for Kale. This step itself makes Chen et al.’s algorithm practical for much larger n than what is observed by Kleindessner et al.

Handling the guesses For all algorithms (except Kleindessner et al.’s), we use . For Chen et al.’s algorithm, we use geometric guessing starting with the lower bound given by the farthest point heuristic (call this Gonzalez’s lower bound). For our two-pass algorithm and Kale’s algorithm, we use geometric guessing starting with the simple lower bound until the upper bound given by an arbitrary solution. The values for the guesses in the coordinator’s algorithm are scaled down by a factor of 5.1. Concretely, let be the maximum among the ’s. Then the guesses take values in , until a feasible solution is found. The factor of 5.1 ensures that when is run with the parameter we end up picking at least k pivots from

We now proceed to present our experiments. To show the efectiveness of our algorithms on massive datasets, we run them on a 100 GB synthetic dataset which is a collection of 4,000,000 points in 1000 dimensional Euclidean space, where each coordinate is a uniformly random real in (0,10000). Each point is assigned one of the four groups uniformly at random, and capacity of each group is set to 2. Just reading this data fle takes more than four minutes. Our two-pass algorithm takes 1.95 hours and our distributed algorithm takes 1.07 hours; both compute a solution of almost the same cost, even though their theoretical guarantees are diferent. Here, we use block size of 10000 in the distributed algorithm, i.e., the number of processors

For the above dataset and the real datasets: The input is read from the input fle and attributes are read from the attribute fle, one data point at a time, and fed to the algorithms. This is done in order to be able to handle the 100 GB dataset. Using Python’s multiprocessing library, we are able to use four cores of the processor 5.

5.1 Real Datasets

We use three real world datasets: Celeb-A [LLWT15], Sushi [sus], and Adult [KB], with n = 1000 by selecting the frst 1000 data points (see Table 2).

Celeb-A dataset is a set of 202,599 images of human faces with attributes including male/female and young/not-young, which we use. We use Keras to extract features from each image [fea] via the pretrained neural network VGG16, which returns a 15360 dimensional real vector for each image. We use the distance as the metric and two settings of groups: male/female with capacity of 2 each (denoted by [2,2] in Table 2), and {male, female} {young, not-young} with capacity of 2 each (denoted by

Sushi dataset is about preferences for diferent types of Sushis by 5000 individuals with attributes of male/female and six possible age-groups. In SushiB, the preference is given by a score whereas in SushiA, the preference is given by an order. For SushiB, we use the distance whereas for SushiA, we use the number of inversions, i.e., the distance between two Sushi rankings is the number of doubletons {i,j} such that Sushi i is preferred over Sushi j by one ranking and not the other. For both SushiA and SushiB, we use three diferent group settings: with gender only, with age group only, and combination of gender and age group. This results in 2, 6, and 12 groups, respectively, and the capacities appear as , respectively, in Table 2.

Table 2: Comparison of solution quality of algorithms for fair k-center on real datasets. Each column after the third corresponds to an algorithm and shows ratio of its cost and Gonzalez’s lower bound. Note that this is not the approximation ratio. Our two-pass algorithm is the best for majority of the settings. Dark shaded cell shows the best-cost algorithm and lightly shaded cell shows the second best.

Motivated by Kleindessner et al., we consider the adult dataset [KB], which is extracted from US census data and contains male/female attribute and six numerical attributes that we use as features. We normalize this dataset to have zero mean and standard deviation of one and use the distance as the metric. There are two attributes that can be used to generate groups: gender and race (Black, White, Asian Pacifc Islander, American Indian Eskimo, and Other). Individually and in combination, this results in 2, 5, and 10 groups, respectively.

For comparison, see Table 2. On majority of settings, our two-pass algorithm outputs a solution with cost smaller than the rest. We reiterate for emphasis that in addition to being at least as good as the best in terms of solution quality, our algorithms can handle massive datasets.

For the distributed algorithm, we use block size of 25, i.e., the number of processors are 1000/25 = 40: theoretically, using processor gives maximum speedup.

5.2 Synthetic Datasets

Motivated by the experiments in Kleindessner et al., we use the Erdős-Rényi graph metric to compare the running time and cost of our algorithms with existing algorithms. For a fxed natural number n, a random metric on n points is generated as follows. First, a random undirected graph on n vertices is sampled in which each edge is independently picked with probability 2logn/n. Second, every edge is assigned a uniformly random weight in (0,1000). The points in the metric correspond to the vertices of the graph, and the pairwise distances between the points are given by the shortest path distance. In addition, if m is the number of groups, then each point in the metric is assigned a group in {1,2,...,m} uniformly and independently at random.

Figure 2 shows the plots between the running time and instance size n; the bottom one is a zoom-in of the top one to the lower four plots. In this experiment, n takes values in {100,150,200,...,350}. The number of groups is fxed to 5 and the capacity of each group is 2. For each fxing of n, we run the fve algorithms on 20 independent random metric instances of size n to compute the average running time. Our two pass algorithm and Kleindessner et al.’s algorithm are the fastest. Our distributed algorithm is

Figure 2: Comparing Running Times

faster than Chen et al.’s algorithm, but slower than Kale’s.

Figure 3 shows the ratios of the cost of various algorithms to Gonzalez’s lower bound. For this comparison, the instance size is fxed to 500 and capacities are [5,5,5],[2,2,11],[2,2,8,8],[3,3,3,11],[1,2,3,4,5], [3,3,4,4,5],[4,4,5,5,5,10],[2,2,2,2,2,2]. Here again, for every fxing of the capacities, the algorithm is run on 20 independent random metric instances to compute the average costs. Chen et al.’s algorithm achieves the least cost for almost all settings, and Kleindessner et al.’s algorithm gives the highest cost on majority (5 out of 8) of settings. Our two-pass algorithm and Kale’s algorithm perform similar to each other and are quite close to Chen et al.’s. Our distributed algorithm is somewhere in between Chen et al.’s and Kleindessner et al.’s. Note that the ratios of the costs between any two algorithms is at most 1.167.

In the implementation of our two pass algorithm, we use geometric guessing starting with the simple lower bound until the algorithm returns a success instead of running all guesses. This is done for a fair comparison in terms of running time.

One research direction is to improve the theoretical bounds, e.g., get a better approximation ratio in the distributed setting or prove a better hardness result. Another interesting direction is to use fair k-center for fair rank aggregation using the number of inversions between two rankings as the metric.

Figure 3: Comparing Approximation Ratios

[AEKM19] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering with- out over-representation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 267–275, 2019.

[BCFN19] Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 4955–4966, 2019.

[BIPV19] Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, and Kasturi Varadarajan. A Constant Approximation for Colorful k-Center. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[CKLV17] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 5029–5037. Curran Associates, Inc., 2017.

[CKSElisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth Vishnoi. Fair and diverse DPP-based data summarization. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Pro-

ceedings of Machine Learning Research, pages 716–725, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.

[CLLW16] Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center prob- lems. Algorithmica, 75(1):27–52, May 2016.

[fea] Keras: Extract features with vgg16. . Accessed: 2020-01-26.

[Gon85] Teoflo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985.

[Guh09] Sudipto Guha. Tight results for clustering and summarizing data streams. In Proc. 12th International Conference on Database Theory, ICDT ’09, pages 268–275, 2009.

[HKK10] MohammadTaghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz. Budgeted red-blue median and its generalizations. In Proceedings of the 18th Annual European Conference on Algorithms: Part I, ESA’10, pages 314–325. Springer-Verlag, 2010.

[HN79] Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3):209 – 215, 1979.

[HS85] Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res., 10(2):180–184, May 1985.

[JSS20] Xinrui Jia, Kshiteej Sheth, and Ola Svensson. Fair colorful k-center clustering. In To appear in

[Kal19] Sagar Kale. Small Space Stream Summary for Matroid Center. In APPROX/RANDOM, volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:22, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[KAM19] Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In ICML, volume 97, pages 3448–3457, Long Beach, California, USA, 09–15 Jun 2019. PMLR.

[KB] Ronny Kohavi and Barry Becker. Adult data set. . Accessed: 2020-01-26.

[KKN11] Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna Saha. The matroid median problem. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, pages 1117–1130, 2011.

[KMM15] Matthew Kay, Cynthia Matuszek, and Sean A. Munson. Unequal representation and gender stereotypes in image search results for occupations. In CHI, pages 3819–3828, 2015.

[LLWT15] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.

[MKC15] Gustavo Malkomes, Matt J Kusner, Wenlin Chen, Kilian Q Weinberger, and Benjamin Moseley. Fast distributed k-center clustering with outliers on massive data. In NIPS, pages 1063–1071. 2015.

[SSS20] Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means. In Evripidis Bampis and Nicole Megow, editors, Approximation and Online Algorithms, pages 232–251, Cham, 2020. Springer International Publishing.

[sus] Sushi preference data sets. . Accessed: 2020-01-26.

The defnition of clustering cost (Defnition 1) immediately implies the following observations.

be sets of points in a metric space given by a distance function d. The clustering cost of A for B is at most the clustering cost of

be sets of points in a metric space given by a distance function d. Suppose the clustering cost of each is at most . Then the clustering cost of is at most

The following lemma follows easily from the triangle inequality.

Lemma 7 (Lemma 1 from the paper, restated). The clustering cost of A for C is at most the clustering cost of A for B plus the clustering cost of B for C.

Proof. Let d be the metric and let denote the clustering costs of A for B and of B for C respectively. For every , there exists . But for this b, there exists such that . Thus, for every , there exists a triangle inequality. This proves the claim.

The pseudocodes of procedures are given by Algorithms 4, 5, and 6 respectively.

Observation 10. The procedure performs a single pass over the input set T . The set P returned by contains points separated pairwise by distance more than r. The clustering cost of P for T is at most r. Therefore, by Lemma 2 from the paper, if there is a set of k points whose clustering cost for T is at most

Observation 11. The procedure executes a single pass over the input set T. The points in each set returned by belong to distinct groups and are all within distance r from p. For every point q within distance contains a point in the same group as q (possibly q itself).

The procedure constructs the following bipartite graph. The left side vertex set contains K vertices: one for each . The right side vertex set is vertices for each group contains a point from group j, then its vertex is connected to the all of . Each matching H in this bipartite graph encodes a feasible subset as follows. For each edge where the point from belonging to group j. Observe that since is a matching, C contains at most points from group j. Moreover, |C| = |H|, and hence, a maximum cardinality matching in the bipartite graph encodes a set C intersecting as many of the ’s as possible.

In our implementation, we enhance the efcienty of as follows. For each group, we introduce only one vertex in the right side vertex set and construct the bipartite graph like directing edges from left to right. We further connect a source to the left side vertices with unit capacity edges, and the right side vertices to a sink with edges of capacities . We fnd the maximum (integral) source-to-sink fow using the Ford-Fulkerson algorithm. For each i and j, if the edge exists and carries nonzero fow, then we include in C the point in that belongs to group j. Our runtime is bounded as follows.

Lemma 8. The runtime of

Proof. The number of edges in the constructed bipartite graph is whereas the value of the max-fow is no more than K. The runtime of the Ford-Fulkerson algorithm is of the order of the size of the number of edges times the value of max-fow. Therefore, the runtime of dominated by the runtime of the Ford-Fulkerson algorithm, turns out to be