Abstract 1 Introduction Organization 2 Preliminaries 3 Proof Overview 4 FPT algorithm for ℓ𝒑-socially fair clustering 5 Local search algorithm for (𝒑,𝒒)-clustering 6 Socially fair facility location References

Socially Fair Clustering: Parameterized Approximation and Local Search

Aditya Anand ORCID Computer Science and Engineering, University of Michigan, Ann Arbor, MI, USA    Yury Makarychev ORCID Toyota Technological Institute at Chicago (TTIC), IL, USA    Liren Shan ORCID Toyota Technological Institute at Chicago (TTIC), IL, USA
Abstract

We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian [2] and by Ghadiri, Samadi, and Vempala [14], along with its extension, the (p,q)-Socially Fair Clustering problem. This problem generalizes k-median and k-means to settings where data points are partitioned into β„“ groups, and the goal is to find a fair clustering that is simultaneously good for all groups. We present several algorithms for this problem.

  1. 1.

    For β„“p-Socially Fair Clustering, we give the first constant-factor FPT-approximation parameterized by the number of groups β„“, resolving the open question raised by Ghadiri, Singh, and Vempala [15]. Our main ingredient is a new algorithm for closing additional centers in parameterized time inspired by local search.

  2. 2.

    We then turn to the more general (p,q)-Socially Fair Clustering problem. The known algorithm for this problem, proposed by ChlamtÑč, Makarychev, and Vakilian [13], achieves a very good approximation but is complex, slow and difficult to implement. We analyze the performance of a simple local search algorithm and show that it provides an O⁒(q)-approximation in the worst case.

  3. 3.

    Finally, we design approximation algorithms for the facility location variant of the problem, where the number of facilities (centers) is not fixed in advance, and opening each facility incurs an opening cost. Unlike in previous work, we do not assume these opening costs are the same for all groups.

Keywords and phrases:
Socially fair clustering, Approximation algorithms, Fixed-parameter tractability, Local search, Facility location, k-median and k-means
Category:
APPROX
Funding:
Yury Makarychev: NSF award ECCS-2216899
Copyright and License:
[Uncaptioned image] © Aditya Anand, Yury Makarychev, and Liren Shan; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation β†’ Facility location and clustering
; Theory of computation β†’ Fixed parameter tractability
Related Version:
Full Version: https://arxiv.org/abs/2608.30026
Editors:
Mohit Singh and Tom Gur

1 Introduction

1.1 Overview

Today, computers are widely used to analyze and classify data, generate recommendations, and make decisions that affect many aspects of people’s lives. Traditionally, algorithms have focused on optimizing the overall quality of a solution. As a result, their decisions may be unfair to specific individuals or groups. Given the significance of these decisions, addressing fairness in algorithmic decision-making has become essential.

The k-median and k-means objectives are widely used in clustering and typically yield solutions that perform well for most data points. However, some points may be much farther from their assigned centers than others, and therefore incur disproportionately high costs. This is especially problematic when data points represent people, and those bearing the highest costs disproportionately belong to minority groups. Consider, for example, a facility location problem modeled using k-median: we wish to open k facilities (e.g., hospitals or grocery stores) in a city to serve all residents effectively. The goal is to minimize the sum of distances from each person (data point) to their nearest facility (center): βˆ‘u∈Xd⁒(u,C). If a minority group resides in an isolated neighborhood, it is possible that none of the facilities will be placed nearby, leaving that group underserved.

To address this issue, [2] and [14] independently introduced the Socially Fair Clustering problem. This problem was also previously studied by [6] in the context of clustering under uncertainty. In the fair clustering setting, the n data points belong to β„“ groups G1,…,Gβ„“βŠ†X, representing minority or otherwise protected populations (the groups may overlap and do not have to cover X). The goal is to find a clustering that performs well for all groups simultaneously. It is convenient to assign weights to data points: for group i, let wi⁒(u) denote the weight of point u, where wi⁒(u)>0 if u∈Gi and wi⁒(u)=0 otherwise; one natural choice is wi⁒(u)=1/|Gi| for u∈Gi.

The β„“p-Socially Fair Clustering problem, referred to as β„“p-Clustering for brevity, asks for a set of k centers C from a set of potential centers FβŠ†X that minimizes

maxi∈{1,…,β„“}(βˆ‘u∈Xwi(u)d(u,C)p)1/p, (1)

ensuring that the solution performs well across all groups. In other words, we compute the p-norm of distances (βˆ‘u∈Xwi⁒(u)⁒d⁒(u,C)p)1/p for each group Gi, and the objective aggregates these by taking a maximum (many papers define the objective as the p-th power of ours; the two formulations are essentially equivalent: an Ξ±-approximation for our objective corresponds to an Ξ±p-approximation for the alternative, and vice versa).

A more general variant of the problem, known as (p,q)-Socially Fair Clustering with 1≀p≀qβ‰€βˆž, employs a different aggregation function.111We assume that qβ‰₯p, since otherwise the objective would favor unfair clusterings. For example, let p=2⁒q and β„“=2. Suppose there are two candidate solutions: in the first, each group has p-norm distance 1, while in the second, the p-norms of the distances for the two groups are 21/p and 0 (where the p-norm distance of group i is given by (βˆ‘u∈Xwi⁒(u)⁒d⁒(u,C)p)1/p). The corresponding aggregated objectives are (11/2+11/2)1/q=21/q and (21/2+01/2)1/q=21/(2⁒q). Thus, we would prefer the second solution, even though it is clearly less fair. In this formulation, we construct a vector whose i-th coordinate represents the p-norm of the distances for group i, and then take the β„“q norm of this vector:

(βˆ‘i=1β„“(βˆ‘u∈Xwi⁒(u)⁒d⁒(u,C)p)q/p)1/q. (2)

We refer to this problem simply as (p,q)-Clustering. When q=∞, the objective in (2) reduces to that in (1); thus, β„“p-Clustering and (p,∞)-Clustering are equivalent. Moreover, the (p,max⁑{p,log⁑ℓ})-objective approximates the β„“p-objective within a constant factor. This follows from the more general fact that the β„“q and β„“r norms of a d-dimensional vector are within a factor of d|1qβˆ’1r| of each other, which can be shown by a simple computation. Hence in all our results for (p,q)-Clustering, we obtain results for β„“p-Clustering by setting q=max⁑{p,log⁑ℓ}.

1.2 Known results

The problem has been extensively studied since its introduction. We begin by summarizing previously published approximation algorithms. [6] gave an O⁒(log⁑n+log⁑ℓ)-approximation for β„“1-Clustering. [2] and [14] provided O⁒(β„“1/p)-approximation algorithms for β„“p-Clustering with p∈{1,2}. Additionally, [2] presented a bicriteria approximation algorithm that achieves a constant-factor approximation by opening O⁒(k) centers.

The approximation factor was later improved by [22], who obtained an O⁒(log⁑ℓlog⁑log⁑ℓ)1/p-approximation. This approximation factor is optimal under the assumption that N⁒PβŠˆβ‹‚Ξ΄>0D⁒T⁒I⁒M⁒E⁒(2nΞ΄), as was shown by [10]. Finally, [13] studied the (p,q)-Clustering problem and gave an O⁒(qln⁑(1+q/p))1/p-approximation for it. This approximation factor matches that for β„“p-clustering when q=log⁑ℓ.

Another line of research has focused on designing fixed-parameter tractable (FPT) algorithms for β„“p-Clustering. In a significant result, [16] settled the approximability of β„“p-Fair Clustering for FPT algorithms parameterized by k by designing a 3+Ξ΅-approximation algorithm and proving a matching lower bound of 3βˆ’Ξ΅. They also established lower bounds of 1+2/eβˆ’Ξ΅ and 1+8/eβˆ’Ξ΅ for the approximability of β„“1 and β„“2-Clustering when parameterized by both k and β„“.

[15] observed that in practice, β„“ is typically a small constant, while k may be very large. They presented a polynomial-time algorithm achieving a 5+2⁒6 bicriteria approximation by opening at most k+β„“ centers. Building on the bicriteria result mentioned above, they also designed algorithms with running times nOp⁒(β„“2) and kℓ⁒poly⁒(n), achieving approximation factors of 5+2⁒6+Ξ΅ and 15+6⁒6+Ξ΅, respectively. The latter is an FPT algorithm parameterized by both k and β„“. They then raised the question of whether there exists a FPT algorithm achieving a constant-factor approximation parameterized solely by β„“. This question remained open until our current work.

We also note that the problem admits a (1+Ξ΅)-approximation when parameterized by k for certain special classes of metric spaces, as shown by [1]. In many real-world applications, the number of centers – typically referred to as facilities in this context – is not fixed in advance. Instead, opening each facility incurs a cost. As is standard, we refer to this setting as the Facility Location problem. [2] presented a 4-approximation algorithm for the Facility Location variant of β„“1-Clustering, assuming homogeneous costs across groups (i.e., the cost of opening a facility is shared equally among all groups).

1.3 Other related work

The theme of fair clustering has received a lot of attention in recent years. Some other notions of fairness that have been adopted include balancedness [11], no over-representation [4], fair hierarchical clustering [3], individual fairness [20], pairwise fairness [9, 8]. Many of these incorporate constraints on clusters rather than enforcing fairness through a new objective, as is the case for Socially Fair Clustering.

1.4 Our results

1.4.1 FPT Algorithm parameterized by β„“

In this paper, we address several important open problems in the field. First, we resolve the open question posed by [15] by presenting a constant-factor approximation FPT algorithm for β„“p-Clustering, parameterized by the number of groups β„“.

Theorem 1.

For every Ξ΅>0, there exists a (17+6⁒6+Ξ΅)-approximation algorithm for β„“p-Clustering that runs in time f⁒(β„“,p,1Ξ΅)β‹…nO⁒(1).

We prove this result by designing a new algorithm that reduces the number of centers in fixed-parameter time.

Theorem 2.

There exists an algorithm that, given an instance of β„“p-Clustering, a c-approximate solution C with k+t centers, and a parameter Ξ΅>0, returns a (3⁒c+2+Ξ΅)-approximate solution with k centers. The algorithm runs in time f⁒(β„“,p,t,1Ξ΅)β‹…nO⁒(1).

Combining Theorem 2 with the following result of [15], we immediately obtain Theorem 1, thereby answering their open question.

Theorem 3 ([15]).

There is a bicriteria polynomial-time algorithm for β„“p-Clustering that finds a (5+2⁒6)-approximate solution with k+β„“ centers.

Additionally, in the full version of this paper, we strengthen Theorem 3 in the important case of β„“1-Clustering by presenting a local-search algorithm that finds a (3+Ξ΅)-approximation with k+f⁒(β„“,1Ξ΅) centers. This yields a variant of the algorithm from Theorem 1 with a (11+Ξ΅)-approximation for β„“1-Clustering.

1.4.2 Local Search Algorithm for (𝒑,𝒒)-Clustering

The second theme of our paper is the design of a more efficient and implementable algorithm for (p,q)-Clustering. The algorithm in [13] solves an exponential-size convex relaxation using the round-or-cut framework, which is impractical and difficult to implement. In contrast, local search algorithms are well known for their efficiency and ease of implementation. Previously, [7] showed how to obtain a (5+Ξ΅)-approximation for k-median using a single-swap local search algorithm, and a (3+Ξ΅)-approximation using a multiple-swap variant. This result was generalized by [17], who gave an O⁒(p)-approximation for the single-group case of β„“p-Clustering and showed that this analysis is tight – there are instances where the algorithm returns only an Ω⁒(p)-approximate solution.

We analyze the performance of the single-swap local search algorithm on instances of (p,q)-Clustering with an arbitrary number of groups β„“, and show that it yields an O⁒(q)-approximation. The aforementioned lower bound in [17] implies that our analysis is tight. While our approximation guarantee is worse than those of [22] and [13], it comes close in a particularly important case: β„“1-Clustering. For that problem, we obtain an O⁒(log⁑ℓ)-approximation by setting q=log⁑ℓ, which matches the best known approximation factor of O⁒(log⁑ℓ/log⁑log⁑ℓ) up to a log⁑log⁑ℓ factor. Our algorithm is simpler, more implementable, and much faster than the algorithm of [13].222The running time in [13] is polynomial, but it is not stated explicitly.

Theorem 4.

There is a single-swap local search algorithm for the (p,q)-Clustering problem that gives an O⁒(q)-approximation, performs at most O⁒(k⁒q⁒log⁑n) iterations and runs in time Op,q⁒(n2⁒ℓ⁒k2⁒log⁑n).

1.4.3 (𝒑,𝒒)-Socially Fair Facility Location

Finally, we study the (p,q)-Socially Fair Facility Location problem, an important and practically motivated variant of (p,q)-Clustering. Building on the result of [2] for β„“1, we present a (4+Ξ΅)-approximation algorithm for (p,q)-Socially Fair Facility Location with homogeneous costs. We then consider a more general setting with heterogeneous costs, where different groups incur different facility opening costs. In this case, we obtain an O⁒(q/log⁑q)-approximation; in particular, for p=1,q=∞, this yields an O⁒(log⁑ℓ/log⁑log⁑ℓ)-approximation333We recall that the (1,log⁑ℓ) objective approximates the (1,∞) objective up to a constant factor, which almost matches the approximation hardness of Ω⁒(log1βˆ’Ξ΅β‘β„“) for this problem; see the full version for details.

Theorem 5.

For Socially Fair Facility Location with group-homogeneous facility cost, there exists a polynomial-time algorithm that achieves a (4+Ξ΅)-approximation for any Ξ΅>0.

Theorem 6.

For Socially Fair Facility Location with group-heterogeneous facility cost, there exists a polynomial-time algorithm that achieves an O⁒(q/log⁑q)-approximation.

Organization

Section 3 gives an overview of the proofs of our results. In Section 4, we present our fixed-parameter tractable (FPT) algorithm for β„“p-Clustering. In Section 5, we analyze a simple single-swap local search algorithm for (p,q)-Clustering. In Section 6, we describe our algorithm for (p,q)-Socially Fair Facility Location. In the full version of the paper, we give a (3+Ξ΅)-bicriteria local-search algorithm that opens k+f⁒(β„“) centers for β„“1-Clustering.

2 Preliminaries

This paper focuses on the β„“p and (p,q)-Fair Clustering Problems, referred to below simply as β„“p- and (p,q)-Clustering. In these problems, we are given a metric space (X,d), where the points represent data points or clients, and a set of potential center or facility locations FβŠ†X. Let n be the number of data points or clients. For each point u∈X, we are also given a vector of weights w⁒(u)βˆˆβ„β‰₯0β„“, where the i-th coordinate wi⁒(u) denotes the weight for group i. We denote the number of groups by β„“. The goal is to select a subset of k centers CβŠ†F that minimizes objective (1) for β„“p-Clustering and (2) for (p,q)-Clustering.

To analyze these objectives, we define the β„“p-cost of the clustering (raised to the power p) with respect to a weight function wi:X→ℝβ‰₯0 and centers C as

cost⁑(wi,C)=βˆ‘u∈Xwi⁒(u)⁒d⁒(u,C)p,

where d⁒(u,C)=minc∈C⁑d⁒(u,c). We then define the cost vector induced by weights w and centers C as the β„“-dimensional vector whose i-th coordinate is cost(wi,C)1/p. Then the β„“p-objective in (1) is the β„“βˆž-norm of the cost vector, while the (p,q)-objective in (2) is its β„“q-norm.

We will need the following claim.

Claim 7 (see e.g. Lemma A.1 in [21]).

For all non-negative real numbers a and b, and for every pβ‰₯1 and Ξ΅>0, we have

(a+b)p≀(1+Ξ΅)pβˆ’1⁒ap+(1+1/Ξ΅)pβˆ’1⁒bp,

3 Proof Overview

In this section, we offer a technical overview of the proofs of our main results. We focus primarily on the fixed-parameter tractable (FPT) approximation algorithm for β„“p-Clustering parameterized by the number of groups β„“ (Section 4), and then briefly describe the ideas underlying the remaining results.

3.1 FPT approximation for ℓ𝒑-Clustering (Section 4)

Our goal is to design a constant-factor approximation algorithm for β„“p-Clustering that runs in time f⁒(β„“)β‹…nO⁒(1), parameterized only by the number of groups β„“. As a starting point, we run the algorithm of [15] (see Theorem 3) to get a (5+2⁒6)-approximate solution with at most k+β„“ centers in polynomial time. In the special case of β„“1-Clustering, we can alternatively use the local-search-based bicriteria approximation algorithm (see the full version of the paper), which yields a better approximation. Let C denote the resulting set of k+t centers, where t=β„“, and let c be the corresponding approximation factor.

Given such a bicriteria solution, the main challenge is to close t centers and reassign the clients assigned to them to other centers, while controlling the cost increase for all groups. We proceed in two steps. First, we show that existentially it is possible to close t centers C1 and reassign every client assigned to a center c in C1 to the center closest to c in Cβˆ–C1 so that the cost of the resulting solution is within a constant factor of the cost of C (see Lemma 9 for the exact guarantee). The key idea is that the new connection cost for a client u can be bounded in terms of both the cost of connecting u to its originally assigned center in C1 and the cost of connecting u to the center serving u in the optimal solution Cβˆ—. This observation is important because it allows us to reassign the clients assigned to the t closed centers to at most t centers (that are not closed), and this property is crucial for our algorithm.

However, we cannot use the procedure from Lemma 9 directly, as it requires knowledge of Cβˆ—. Thus, to obtain an FPT algorithm, we need to identify the set C1 without access to the optimal solution. This is achieved using the technique of color coding introduced by [5]. Let C2βŠ†Cβˆ–C1 be the set formed by selecting, for each c∈C1, a closest center to c in Cβˆ–C1. Note that |C2|≀|C1|=t (each center c1∈C1 contributes at most one selected center; and different centers in C1 may potentially have the same closest center in Cβˆ–C1). We color all centers in C randomly using two colors, red and blue. Each center is colored red or blue independently with probability 1/2. Note that with probability at least 2βˆ’2⁒t, all centers in C1 are colored red and all centers in C2 are colored blue. By running the algorithm O⁒(22⁒t⁒log⁑n) times, we obtain a coloring with this property with high probability. We denote the sets of red and blue centers by R and B, respectively.

Now, we introduce the notion of a Z-profile of a center c. Loosely speaking, the Z-profile is a vector in ℝℓ that captures, for each of the β„“ groups, the reassignment cost incurred by closing center c and reassigning all clients assigned to c to the center closest to c in Z. Crucially, the C2-profiles of all centers in C1 fully determine the reassignment cost: the reassignment cost vector is simply the sum of the C2-profiles of all centers in C1. Importantly, if we were to find another set of centers in R with the same profiles, the reassignment cost would be the same. However, there are two challenges in finding such a set. First, as defined, the number of possible profiles is unbounded. Second, since we do not know the set C2, we cannot compute the C2-profiles of centers in R.

To resolve the first issue, we discretize the set of all possible profiles so that their number is bounded by a function of β„“, t, p, and 1/Ξ΅. We then β€œguess” the number of centers in C1 with each possible profile. Next, we observe that the C2-profiles and B-profiles of centers in C1 are equal, and thus we can use B as a proxy for C2. We select centers in R according to our guess of the profile counts and obtain a set D1 of t centers to close. Given the discussion above, it is not hard to see that by closing the centers in D1 and reassigning clients to their closest centers in B, we obtain a constant-factor approximation.

3.2 Local search for (𝒑,𝒒)-Clustering (Section 5)

Building on the local search algorithms from [7] and [17] for k-median, k-means, and (k,p)-clustering, we design and analyze a local search algorithm for the more general (p,q)-Clustering problem. The general approach is similar to that of [7] and [17], but the analysis is more complex, as it requires fine-grained control over the distribution of swaps (see below).

The algorithm starts with an arbitrary set C of k centers and repeatedly finds and performs a swap cβ†’cβ€² that replaces one of the centers c∈C with a center cβ€² outside of C. The swaps are chosen to minimize the (p,q)-Clustering objective, and the algorithm terminates when no swap decreases the current potential Ξ¦ by more than Ξ¦/(8⁒k). To prove that the algorithm achieves an O⁒(q)-approximation, we show that if the cost of the current solution exceeds the optimal cost by Ω⁒(q) times, then there must exist an improving swap. To this end, we present a distribution over special swaps that replace centers in C with centers in an unknown optimal solution Cβˆ— (The algorithm may choose a swap from the distribution or any other swap improving the objective; we use the distribution only for the analysis). While this approach resembles that of [7] and [17], we require significantly more control over the distribution of swaps to handle the more complex objective. In particular, we use careful linear approximations for the change in the non-linear objective that allow us to show that there is indeed such a distribution over improving swaps.

To obtain these linear approximations, roughly speaking, we can obtain upper and lower bounds on the derivative of the cost function in the desired range. One can then use the mean-value theorem to find a linear approximation of the change in the objective using these bounds. The actual proof is slightly different, and uses convexity arguments along with the mean value theorem. Carefully combining this with the standard linear-objective analysis for k-Median, we show that the algorithm is an O⁒(q) approximation.

3.3 Socially Fair Facility Location (Section 6)

Finally, we study (p,q)-Socially Fair Facility Location. We consider two variants of the problem: facility location with homogeneous opening costs and facility location with heterogeneous opening costs. For the homogeneous case, we use a rounding algorithm inspired by the standard facility location algorithm of [23]. For the heterogeneous case, we replace the greedy step that selects and opens the cheapest facility within a certain ball Bu with a randomized rounding step that opens a facility in Bu with probability proportional to the target probability given by the convex relaxation. We then use Rosenthal’s inequality to bound the expected β„“q-norm of the solution. We also give a hardness result showing that our algorithm is near-optimal for β„“1-Socially Fair Facility Location (the case when p=1, q=∞).

4 FPT algorithm for ℓ𝒑-socially fair clustering

As discussed in the introduction, we provide an FPT algorithm for β„“p-Clustering, parameterized by the number of groups β„“. The algorithm first finds an approximate solution with k+t centers using Theorem 3. This solution provides only a bicriteria approximation. To obtain a true approximation, the algorithm closes t centers – using Theorem 2.

We now proceed with the proof of Theorem 2. Given the instance of ℓp-Clustering on point set X and metric d, a set of centers C and an assignment α:X→C, we define the cost with respect to the weight function wi and assignment α as follows:

costi⁑(Ξ±)=cost⁑(wi,Ξ±) :=βˆ‘u∈Xwi⁒(u)⁒d⁒(u,α⁒(u))p.

Note that the β„“p-objective function for the assignment Ξ± is then maxi∈[β„“]costi(Ξ±)1/p. Throughout this section, we fix an optimal set of centers Cβˆ— and a corresponding optimal assignment Ξ²βˆ—. Let us define OPT to be the optimal assignment β„“p-objective, so that OPT=maxicosti(Ξ²βˆ—)1/p.

First, we show that given any set C of k+t centers which is a c-approximate solution, indeed there exists a subset of t centers that can be closed such that the resulting subset of k-centers is a (3⁒c+2)-approximate solution. However, besides this, we show a stronger property that our algorithm requires: every client assigned to some center of C (in an optimal assignment of clients to C) that is closed in this process can now be reassigned to one of at most t open centers in C. The next key lemma proves this result. Before we state the lemma, the following definition will be useful.

Definition 8.

Given a set of open centers C, an assignment Ξ±:Xβ†’C of points to centers in C, and two disjoint subsets C1,C2βŠ†C, we define a new assignment Ξ±β€² obtained from Ξ± by reassigning clients as follows. For each client u∈X, if α⁒(u)∈C1, we find the closest center c2 in C2 to c1≑α⁒(u) and let α′⁒(u)=c2. If α⁒(u)βˆ‰C1, we set α′⁒(u)=α⁒(u) (do not change the assignment).

We then define cost⁑(Ξ±,C1,C2) to be the vector (v1,v2,…,vβ„“) with vi=costi⁑(Ξ±β€²)βˆ’costi⁑(Ξ±) for each i∈[β„“].

Simply put, costi⁑(α,C1,C2) measures the increase in cost for group (coordinate) i by re-assigning each point assigned to a center c1∈C1 to the center in C2 closest to c1. We use the shorthand cost⁑(β,c1,C2) to denote cost⁑(β,{c1},C2). If β is an optimal assignment, then cost⁑(β,c1,C2) is coordinatewise non-negative, since any reassignment can only increase the cost. We also have:

cost⁑(Ξ²,C1,C2)=βˆ‘c1∈C1cost⁑(Ξ²,c1,C2) (3)

We formalize this nearest-neighbor redirection operation in the following lemma, showing that one can close a set C1 of t centers and reassign all affected clients to a set C2 of at most t receiving centers while keeping the reassignment cost controlled. The redirection operator in the definition captures exactly what happens when we close centers C1βŠ†C: for each closed center c1∈C1, we send all of its clients to the closest open center c2∈Cβˆ–C1. Let C2 be the set of such receiving centers.

Lemma 9.

Given a c-approximate solution C with k+t centers and a corresponding optimal assignment Ξ² of clients to centers in C, there exist disjoint sets C1,C2βŠ†C with |C2|≀|C1|=t such that

  • β– 

    β€–cost⁑(Ξ²,C1,C2)β€–βˆžβ‰€((3⁒c+2)pβˆ’cp)⁒OPTp

  • β– 

    C2={c2:c2 is the closest point from Cβˆ–C1 to c1 for some c1∈C1}.

Proof.

Let Cβˆ—={c1βˆ—,c2βˆ—,…,ckβˆ—} be an optimal set of centers, and let Ξ²βˆ— be an optimal assignment of clients to the centers in Cβˆ—. For each ciβˆ—, mark γ⁒(ciβˆ—)∈C, the closest center to ciβˆ— in C. Then there are at most k marked centers in C and at least t unmarked ones. Choose any subset of t unmarked centers in C to be the set C1. For each center of C1, we take the closest center in Cβˆ–C1 to obtain the set C2. Note that this means |C2|≀|C1|.

We now show that this choice of C1,C2 satisfies the statement of the lemma. Let c1∈C1 and let c2 be the closest center to c1 in Cβˆ–C1 (which must be in C2). Then, for every point u∈X with β⁒(u)=c1, we reassign u to c2.

We wish to bound the reassignment cost of u to c2. Let cβˆ—=Ξ²βˆ—β’(u) be u’s assigned center in Cβˆ—. By the triangle inequality,

d⁒(u,c2) ≀d⁒(u,c1)+d⁒(c1,c2)
≀d⁒(u,c1)+d⁒(c1,γ⁒(cβˆ—))⁒(c2Β is the closest center toΒ c1Β inΒ Cβˆ–C1)
≀d⁒(u,c1)+d⁒(c1,cβˆ—)+d⁒(cβˆ—,γ⁒(cβˆ—))
≀d⁒(u,c1)+2⁒d⁒(c1,cβˆ—)⁒(by definition of γ⁒(cβˆ—))
≀d⁒(u,c1)+2⁒(d⁒(u,c1)+d⁒(u,cβˆ—))⁒(again by triangle inequality)
≀3⁒d⁒(u,c1)+2⁒d⁒(u,cβˆ—)

It follows from Claim 7 that for every Ξ΄>0, we get the inequality

d⁒(u,c2)p≀3p⁒d⁒(u,c1)p⁒(1+Ξ΄)pβˆ’1+2p⁒d⁒(u,cβˆ—)p⁒(1+1Ξ΄)pβˆ’1

We can now use this to bound the change in cost. By definition, it follows that the contribution of client u to costi⁑(Ξ²,C1,C2) is wi⁒(u)⁒(d⁒(u,c2)pβˆ’d⁒(u,c1)p). Now repeating the analysis for each point u, and recalling that c1=β⁒(u),cβˆ—=Ξ²βˆ—β’(u), we obtain

costi⁑(Ξ²,C1,C2)≀ βˆ‘u∈Xwi(u)(3p(1+Ξ΄)pβˆ’1d(u,Ξ²(u))p
+2p(1+1Ξ΄)pβˆ’1d(u,Ξ²βˆ—(u))pβˆ’d(u,Ξ²(u))p)
≀ ((3⁒c)p⁒(1+Ξ΄)pβˆ’1+2p⁒(1+1Ξ΄)pβˆ’1βˆ’cp)⁒OPTpfor each ⁒i∈[β„“],

where we use the fact that βˆ‘u∈Xwi⁒(u)⁒d⁒(u,Ξ²βˆ—β’(u))p≀OPTp and βˆ‘u∈Xwi⁒(u)⁒d⁒(u,β⁒(u))p≀cp⁒OPTp, since C is a c-approximate solution.

Now we set δ=23⁒c. It then follows that

costi⁑(Ξ²,C1,C2)≀((3⁒c+2)pβˆ’cp)⁒OPTp.

β—€

Next, we describe how to find such sets in FPT time. We will use the color coding technique of [5]. We remark that while our algorithm is stated as a randomized algorithm for simplicity, it can be easily derandomized using standard techniques (see, for example, [12, Lemma 1]).

Lemma 10.

Given a c-approximate solution C with k+t centers and a corresponding optimal assignment Ξ² of clients to centers in C, one can find disjoint sets D1,D2 with |D2|≀|D1|=t satisfying β€–cost⁑(Ξ²,D1,D2)β€–βˆžβ‰€((3⁒c+2)pβˆ’cp+Ξ΅p)⁒OPTp in time f⁒(β„“,t,p,1Ξ΅)⁒nO⁒(1).

Proof.

Let C1,C2βŠ†C be the (unknown) subsets of C guaranteed by Lemma 9. We use color coding. Randomly and independently color each center in C red or blue, each with probability 1/2. Call a coloring good if every center of C1 is colored red and every center of C2 is colored blue. Then a random coloring is good with probability at least 2βˆ’2⁒t. By independently sampling O⁒(22⁒t⁒log⁑n) random colorings, we can ensure that we enumerate a good coloring with high probability. Henceforth, assume that we are given a good coloring (we will try all the O⁒(22⁒t⁒log⁑n) colorings). Let RβŠ†C be the red-colored centers, and BβŠ†C be the blue-colored centers in this good coloring.

For a set ZβŠ†C, we say that the Z-profile of c∈C is (i1,i2,…,iβ„“) if the m-th coordinate of cost⁑(Ξ²,c,Z) is in the interval [(imβˆ’1)⁒Ρpt⁒OPTp,im⁒Ρpt⁒OPTp] for each m∈[β„“]. Here i1,i2⁒…⁒iβ„“ are positive integers. Let 𝒫 be the set of profiles with all ij≀t⁒(3⁒c+2Ξ΅)p. Then |𝒫|≀(t⁒(3⁒c+2Ξ΅)p)β„“. Note that the C2-profile of every c1∈C1 lies in 𝒫. This is the case because, for every coordinate i∈[β„“], (1) costi⁑(Ξ²,c1,C2)β‰₯0, since Ξ² is an optimal assignment, and (2) costi⁑(Ξ²,c1,C2)≀costi⁑(Ξ²,C1,C2)≀‖cost⁑(Ξ²,C1,C2)β€–βˆžβ‰€(3⁒c+2)p⁒OPTp by (3) and Lemma 9.

For each profile Pβˆˆπ’«, guess the number of centers in C1 with C2-profile P. Let nP denote this number for each P. Then βˆ‘Pβˆˆπ’«nP=|C1|=t. The number of guesses we need to make is at most |𝒫|t≀(t⁒(3⁒c+2Ξ΅)p)ℓ⁒t.

Consider c1∈C1 and let c2 be the closest point to c1 in Cβˆ–C1. Note that c2∈C2 (per item 2 in Lemma 9) and c2 is also the closest point to c1 in B, since c2∈C2βŠ†BβŠ†Cβˆ–C1. Therefore, the C2- and B-profiles of c1 are the same. In particular, there are nP centers with B-profile P in C1. Since all centers in C1 are red (recall that we assumed that the coloring is good), there are at least nP red centers with B-profile P.

Now for each Pβˆˆπ’«, we choose exactly nP red centers whose B-profile is P to form the set D1444While we do not know O⁒P⁒T, we can guess O⁒P⁒Tp up to a factor of (1+Ξ΅), but we omit this detail in the proof for the sake of simplicity. Once we choose D1, we let D2 be the set of all centers d2∈B such that d2 is the closest center in B to some d1∈D1. This concludes the construction of the sets D1 and D2.

Lemma 11.

β€–cost⁑(Ξ²,D1,D2)β€–βˆžβ‰€((3⁒c+2)pβˆ’cp+Ξ΅p)⁒OPTp.

Proof.

There is a one-to-one map f:C1β†’D1 such that the C2-profile of c1 and the B-profile of d1=f⁒(c1) are the same for every c1∈C1.

It follows that for every d1∈D1 and every coordinate i∈[β„“],

costi⁑(Ξ²,d1,D2)=costi⁑(Ξ²,d1,B)≀costi⁑(Ξ²,fβˆ’1⁒(d1),C2)+Ξ΅pt⁒OPTp.

The term Ρpt⁒OPTp is exactly the length of an interval in the definition of profiles. Summing this upper bound on cost⁑(β,d1,B) over all d1∈D1 and using (3), we get

costi⁑(Ξ²,D1,D2) =βˆ‘d1∈D1costi⁑(Ξ²,d1,D2)
β‰€βˆ‘d1∈D1(costi⁑(Ξ²,fβˆ’1⁒(d1),C2)+Ξ΅pt⁒OPTp)
≀costi⁑(Ξ²,C1,C2)+Ξ΅p⁒OPTp≀((3⁒c+2)pβˆ’cp+Ξ΅p)⁒OPTp.

β—€ β—€

Proof of Theorem 2.

Let Ξ² be an optimal assignment for the center set C. Invoke Lemma 10 to obtain the sets D1,D2. After obtaining the sets D1,D2, we close the centers D1. Since |D1|=t, it follows that we obtain a solution with at most k centers.

We have β€–cost⁑(Ξ²)β€–βˆžβ‰€cp⁒OPTp, and by Lemma 10, the additional cost incurred is at most β€–cost⁑(Ξ²,D1,D2)β€–βˆžβ‰€((3⁒c+2)pβˆ’cp+Ξ΅p)⁒OPTp. Thus the β„“p-objective of the resulting solution with k centers is at most ((3⁒c+2)pβˆ’cp+Ξ΅p+cp)1/p⁒OPT≀(3⁒c+2+Ξ΅)⁒OPT where in the final step we use the inequality (a+b)1/p≀a1/p+b1/p, which holds for every pβ‰₯1,a,bβ‰₯0.β—€

By Theorem 3 of [15], we can find a c=5+2⁒6-approximate solution with k+β„“ centers in polynomial time. By Lemma 10, we can close β„“ centers in this bicriteria approximation solution to get a solution with k centers in time (ℓ⁒(3⁒c+2Ξ΅)p)β„“2⁒nO⁒(1). This proves Theorem 1.

5 Local search algorithm for (𝒑,𝒒)-clustering

5.1 Local search with scalar costs

Following [7] and [17], we first revisit the local search algorithm for (k,p)-clustering. We will later apply the results of this section to analyze the performance of the local search algorithm for (p,q)-Clustering.

Let (X,d) be a metric space, and let w⁒(u) be non-negative vertex weights. We consider one step of the local search algorithm. Let C={c1,…,ck} be the current set of k centers, and Cβˆ—={c1βˆ—,…,ckβˆ—} be a target set. Later, Cβˆ— will be an optimal solution for the (p,q)-objective, but for now, we make no assumptions about it.

We define the cost of C as

cost⁑(w)=cost⁑(w,C)=βˆ‘u∈Xw⁒(u)⁒d⁒(u,C)p,

and the cost of Cβˆ— as

costβˆ—β‘(w)=cost⁑(w,Cβˆ—)=βˆ‘u∈Xw⁒(u)⁒d⁒(u,Cβˆ—)p.

Consider a swap operation caβ†’cbβˆ— that replaces ca with cbβˆ—. We denote the resulting set of centers by

Ca⁒b=(Cβˆ–{ca})βˆͺ{cbβˆ—},

and its cost by costa⁒b⁑(w)=cost⁑(w,Ca⁒b)=βˆ‘u∈Xw⁒(u)⁒d⁒(u,Ca⁒b)p.

Consider a probability distribution π’Ÿ on the set of swaps caβ†’cbβˆ— (equivalently, on [k]Γ—[k]). The expected cost after a random swap drawn from π’Ÿ is 𝔼(a,b)βˆΌπ’Ÿβ’[costa⁒b⁑(w)].

We derive the following guarantees for local search. Conceptually, the proof closely follows the analyses in [7] and [17]. However, the bounds we require are more intricate, as we need finer control over the distribution of swaps. We prove this lemma in Section 5.4.

Lemma 12.

Let (X,d) be a metric space, and let C and Cβˆ— be two sets of centers. There exists a probability distribution π’Ÿ over swaps such that the following holds. For every pβ‰₯1, weights w, parameters Mβ‰₯m>0, and coefficients ΞΎa⁒b∈[m,M], we have:

  1. 1.

    For α=10⁒M⁒pm, the following inequality holds.

    π”Όπ’Ÿβ’[ΞΎa⁒bβ‹…(costa⁒b⁑(w)βˆ’cost⁑(w))]≀m2⁒k⁒(Ξ±p⁒costβˆ—β‘(w)βˆ’cost⁑(w)) (4)
  2. 2.

    We also have:

    π”Όπ’Ÿβ’[ΞΎa⁒bβ‹…(costa⁒b⁑(w)βˆ’cost⁑(w))]≀(1+22⁒p)⁒Mk⁒(costβˆ—β‘(w)+cost⁑(w)) (5)
  3. 3.

    Finally, for every swap caβ†’cbβˆ— in the support of π’Ÿ and every Ξ΄0∈(0,1/4), we have

    costa⁒b⁑(w)≀(1+ΞΈ0)⁒costβˆ—β‘(w)+(1+Ξ΄0)⁒cost⁑(w), (6)

    where ΞΈ0=2p⁒(5⁒p/(4⁒δ0))pβˆ’1.

At a high level, the necessity for such guarantees is as follows. In k-median, the objective is linear, and the effects of the change in cost due to a single swap can be directly accounted for. However, in (p,q)-Clustering, the objective involves two layers of non-linearity (the inner and outer norms). To deal with this non-linearity, we can write the change in the objective for each swap caβ†’cbβˆ— as a linear change with multipliers ΞΎa⁒b using the mean value theorem and convexity. Here the multipliers ΞΎa⁒b are bounded in the range [m,M] for some appropriate choice of m and M. The above lemma then assumes this boundedness of ΞΎa⁒b and derives guarantees on the change in cost⁑(w), which in turn bounds the change in the objective.

5.2 Single swap analysis w.r.t. the (𝒑,𝒒)-objective

Now we consider the local search algorithm for (p,q)-Clustering – the goal is to minimize the following objective function:

(βˆ‘i=1β„“(βˆ‘u∈Xwi(u)d(u,C)p)q/p)1/q=(βˆ‘i=1β„“cost(wi,C)q/p)1/q

From now on, let Cβˆ— be an optimal solution for the (p,q)-Clustering problem. We assume that swap caβ†’cbβˆ— is sampled from distribution π’Ÿ constructed in Lemma 12. Define r=q/p and φ⁒(t)=tr, and

zi =cost⁑(wi), ziβ€² =costa⁒b⁑(wi), ziβˆ— =costβˆ—β‘(wi)
Ξ¦ =βˆ‘i=1ℓφ⁒(zi), Ξ¦a⁒b =βˆ‘i=1ℓφ⁒(ziβ€²), Ξ¦βˆ— =βˆ‘i=1ℓφ⁒(ziβˆ—)

Note that (Ξ¦βˆ—)1/q is the cost of the optimal solution, Ξ¦1/q is the cost of the current solution, and Ξ¦a⁒b1/q is the cost of the solution after a swap caβ†’cbβˆ—. Also, let

Ξ”i=𝔼⁒[φ⁒(ziβ€²)βˆ’Ο†β’(zi)].

Fix a coordinate i. Now we get an upper bound for φ⁒(ziβ€²) by approximating Ο† with a piecewise linear function. Let z^i be the maximum of ziβ€² over all swaps in the support of π’Ÿ (we will obtain an upper bound on z^i later using Lemma 12, item 3). Let M=φ⁒(z^i)βˆ’Ο†β’(zi)z^iβˆ’zi and m=φ⁒(zi)/zi=zirβˆ’1. Note that M≀φ′⁒(z^i) when z^i>zi, by the Mean Value Theorem and monotonicity of Ο†β€². Since Ο† is convex, we have (see Figure 1)

Figure 1: We approximate φ⁒(ziβ€²) on the interval [0,z^i] using a piecewise linear function consisting of two segments: the first with slope m, and the second with slope M.
φ⁒(ziβ€²)≀{φ⁒(zi)+mβ‹…(ziβ€²βˆ’zi),if ⁒ziβ€²<ziφ⁒(zi)+Mβ‹…(ziβ€²βˆ’zi),if ⁒ziβ€²β‰₯zi

Define coefficients ξa⁒b as follows

ΞΎa⁒b={m,if ⁒ziβ€²<ziM,otherwise

Then φ⁒(ziβ€²)≀φ⁒(zi)+ΞΎa⁒bβ‹…(ziβ€²βˆ’zi), and we have Ξ”i≑𝔼⁒[φ⁒(ziβ€²)βˆ’Ο†β’(zi)]≀𝔼⁒[ΞΎa⁒bβ‹…(ziβ€²βˆ’zi)].

We are now in a position to use Lemma 12, from which we derive the following key inequality, whose proof is deferred to Section 5.5.

Ξ”i≀14⁒k⁒(Ξ²q⁒φ⁒(ziβˆ—)βˆ’Ο†β’(zi)) (7)

with Ξ²=O⁒(q). Adding up the inequality over all coordinates i∈[β„“], we get

𝔼⁒[Ξ¦a⁒bβˆ’Ξ¦]=βˆ‘i=1β„“Ξ”i≀14⁒k⁒(Ξ²qβ’Ξ¦βˆ—βˆ’Ξ¦).

In particular, this means that there is always a swap caβ†’cbβˆ—, for which

Ξ¦a⁒bβˆ’Ξ¦β‰€14⁒k⁒(Ξ²qβ’Ξ¦βˆ—βˆ’Ξ¦).

5.3 Putting everything together

Consider the local search algorithm that at each iteration finds a swap caβ†’cβ€² with ca∈C and cβ€²βˆˆFβˆ–C that produces the greatest decrease in the potential function Ξ¦, where C is the current set of open centers and F is the candidate facility set. The algorithm terminates when no swap decreases the current potential Ξ¦ by more than Ξ¦8⁒k.

5.3.1 Bounding the number of iterations

Suppose that Ξ¦>2⁒βqβ’Ξ¦βˆ—. Then, for the improving swap caβ†’cbβˆ— identified above, we have

Ξ¦a⁒bβˆ’Ξ¦β‰€βˆ’Ξ¦8⁒k

and

Ξ¦a⁒bβˆ’Ξ¦βˆ—β‰€(Ξ¦βˆ’Ξ¦βˆ—)βˆ’Ξ¦8⁒k≀(1βˆ’18⁒k)⁒(Ξ¦βˆ’Ξ¦βˆ—).

Thus when the algorithm stops, we must have Φ≀2⁒βqβ’Ξ¦βˆ—. Until the algorithm stops, in every iteration, the above inequality holds. It follows that after at most 8⁒k⁒loge⁑(Ξ¦/Ξ¦βˆ—) iterations, the algorithm will find a clustering of cost at most 21/qβ‹…Ξ²β‹…(Ξ¦βˆ—)1/q.

As is standard, by truncating distances and rounding weights, we may assume that all distances and weights are integers bounded polynomially in n. Therefore, the cost of any clustering is polynomial in n; hence, loge⁑(Ξ¦/Ξ¦βˆ—) is bounded by O⁒(q⁒log⁑n). We conclude that the algorithm returns a solution of cost at most O⁒(q)⁒OPT in at most O⁒(q⁒k⁒log⁑n) iterations.

5.3.2 Running time per iteration

In each iteration, we maintain the current set of centers C. For each point u, we maintain its closest and second-closest centers s1⁒(u) and s2⁒(u) in C. At the beginning of every iteration, these quantities can be computed in time O⁒(n⁒k). We can compute the change in cost due to a swap aβ†’b for each point u using s1⁒(u),s2⁒(u) and the distances d⁒(u,a),d⁒(u,b). Then we add these costs for each group in time Op,q⁒(n⁒ℓ) and re-compute the potential. Thus, for every swap aβ†’b, we spend time Op,q⁒(n⁒ℓ) and there are O⁒(n⁒k) swaps, giving a per-iteration running time of O⁒(n2⁒k⁒ℓ). Since there are O⁒(k⁒q⁒log⁑n) iterations, the running time is at most Op,q⁒(n2⁒ℓ⁒k2⁒log⁑n). This concludes the proof of Theorem 4.

5.4 Proof of Lemma 12

In this Section, we prove Lemma 12.

Proof.
Defining the distribution of swaps.

For each center cbβˆ—βˆˆCβˆ—, let γ⁒(cbβˆ—) denote the nearest center in C (see Figure 2). We partition the centers in C based on the number of preimages under Ξ³:

Figure 2: The left figure shows the map Ξ³ that maps every optimal center ciβˆ— to the closest current center cj. This map defines the partition of the optimal centers into sets B1 and B⋆ and the current centers into sets A0, A1, and A⋆. The right figure illustrates two possible types of swaps caβ†’cb.
  • β– 

    A1: centers with exactly one preimage,

  • β– 

    A0: centers with no preimages,

  • β– 

    A⋆: centers with two or more preimages.

Define B1=Ξ³βˆ’1⁒(A1) and B⋆=Ξ³βˆ’1⁒(A⋆). We observe:

  • β– 

    Ξ³ is a one-to-one map between B1 and A1,

  • β– 

    Ξ³ maps B⋆ onto A⋆, with every c∈A⋆ having at least two preimages.

Denote s=|A1|. From the observations above, we get |B1|=|A1|=s and |A⋆|≀|B⋆|/2=(kβˆ’s)/2. Thus, |A0|=kβˆ’|A1|βˆ’|A⋆|β‰₯(kβˆ’s)/2. Now we are ready to define a probability distribution π’Ÿ over swaps.

  1. 1.

    With probability sk, select cbβˆ—βˆˆB1 uniformly at random and set ca=γ⁒(cbβˆ—)∈A1,

  2. 2.

    With probability kβˆ’sk, select ca uniformly from A0 and cbβˆ— uniformly from B⋆.

This yields a random swap caβ†’cbβˆ—. Note that b is uniformly distributed in [k] and therefore the probability that b=b0 is 1/k for every fixed b0∈[k]. In general, a is not uniformly distributed; however, for every fixed a0∈[k], the probability that a=a0 is at most max⁑(skβ‹…1|A1|,kβˆ’skβ‹…1|A0|)≀max⁑(1/k,2/k)=2/k:

Pr⁑{a=a0}≀2/kandPr⁑{b=b0}=1/k (8)

We will need below that for all t≠b,

γ⁒(ctβˆ—)β‰ ca. (9)

Indeed, in item 1, Ξ³βˆ’1⁒(ca)={cbβˆ—}; in item 2, Ξ³βˆ’1⁒(ca)=βˆ…. In either case, ctβˆ—βˆ‰Ξ³βˆ’1⁒(ca).

Upper bounding connection cost

Let xu=d⁒(u,C) denote the distance from u to the closest center in the current solution C, xuβ€²=d⁒(u,Ca⁒b) the updated distance after the swap, and xuβˆ—=d⁒(u,Cβˆ—) the distance to the closest center in Cβˆ—. Let Va be the Voronoi cell of ca in C, and Vbβˆ— the Voronoi cell of cbβˆ— in Cβˆ—. For u∈Vbβˆ—,

xu′⁣pβˆ’xup≀xuβˆ—pβˆ’xup.

For u∈Vaβˆ–Vbβˆ—, assume u∈Vtβˆ— for some tβ‰ b. By (9), γ⁒(ctβˆ—)β‰ ca; thus, γ⁒(ctβˆ—)∈Ca⁒b and

Figure 3: We assign point u to γ⁒(ctβˆ—), which is guaranteed to be in Ca⁒b. The distance from u to γ⁒(ctβˆ—) is upper bounded by d⁒(u,ctβˆ—)+d⁒(ctβˆ—,γ⁒(ctβˆ—)). Further, d⁒(ctβˆ—,γ⁒(ctβˆ—))≀d⁒(ctβˆ—,ca), since γ⁒(ctβˆ—) is the closest current center to ctβˆ—. In turn, d⁒(ctβˆ—,ca) is upper bounded by d⁒(ctβˆ—,u)+d⁒(u,ca).
xuβ€² =d⁒(u,Ca⁒b)≀d⁒(u,γ⁒(ctβˆ—))≀d⁒(u,ctβˆ—)+d⁒(ctβˆ—,γ⁒(ctβˆ—))≀d⁒(u,ctβˆ—)+d⁒(ctβˆ—,ca)
≀d⁒(u,ctβˆ—)+(d⁒(ctβˆ—,u)+d⁒(u,ca))=2⁒xuβˆ—+xu.

Here, we used that d⁒(ctβˆ—,γ⁒(ctβˆ—))≀d⁒(ctβˆ—,ca), since γ⁒(ctβˆ—) is the nearest center in C to ctβˆ—.

Applying Claim 7 with Ξ΄=(1+Ξ΅)pβˆ’1βˆ’1 and ΞΈ=2p⁒(1+1/Ξ΅)pβˆ’1, we get

xu′⁣p≀(xu+2⁒xuβˆ—)p≀(1+Ξ΄)⁒xup+θ⁒xuβˆ—p.

Thus,

xu′⁣pβˆ’xup≀δ⁒xup+θ⁒xuβˆ—p.

Finally, if uβˆ‰VaβˆͺVbβˆ—, then xu′≀xu. We have,

costa⁒b⁑(w)βˆ’cost⁑(w) β‰€βˆ‘u∈Vbβˆ—wu⁒(xu′⁣pβˆ’xup)+βˆ‘u∈Vaβˆ–Vbβˆ—wu⁒(xu′⁣pβˆ’xup) (10)
β‰€βˆ‘u∈Vbβˆ—wu⁒(xuβˆ—pβˆ’xup)+βˆ‘u∈Vawu⁒(δ⁒xup+θ⁒xuβˆ—p). (11)

We now derive an upper bound for ΞΎa⁒bβ‹…(costa⁒b⁑(w)βˆ’cost⁑(w)). Since 0<m≀ξa⁒b≀M, we can replace ΞΎa⁒b with M in positive terms and with m in negative terms. We have:

ΞΎa⁒bβ‹…(costa⁒b⁑(w)βˆ’cost⁑(w))β‰€βˆ‘u∈Vbβˆ—wu⁒(M⁒xuβˆ—pβˆ’m⁒xup)+Mβ’βˆ‘u∈Vawu⁒(δ⁒xup+θ⁒xuβˆ—p)

Now we assume that the swap caβ†’cbβˆ— is sampled from the distribution π’Ÿ defined above. We get

𝔼⁒[ΞΎa⁒bβ‹…(costa⁒b⁑(w)βˆ’cost⁑(w))]
β‰€βˆ‘u∈XPr⁑{u∈Vbβˆ—}β‹…wu⁒(M⁒xuβˆ—pβˆ’m⁒xup)+Mβ’βˆ‘u∈XPr⁑{u∈Va}β‹…wu⁒(δ⁒xup+θ⁒xuβˆ—p)

From 8, we get Pr⁑{u∈Vbβˆ—}=1k and Pr⁑{u∈Va}≀2k and thus

k⁒𝔼⁒[ΞΎa⁒bβ‹…(costa⁒b⁑(w)βˆ’cost⁑(w))]≀(1+2⁒θ)⁒M⁒costβˆ—β‘(w)βˆ’(mβˆ’2⁒δ⁒M)⁒cost⁑(w). (12)

We will use (12) to derive (4), (5), and (6). We will use different values of parameters Ξ΅, Ξ΄, and ΞΈ in these derivations. We will need the following lemma.

Lemma 13.

For every pβ‰₯1 and every value of Ξ΄0∈(0,1/4), there exists Ξ΅>0 such that Ξ΄=(1+Ξ΅)pβˆ’1βˆ’1≀δ0 and θ≀2p⁒(5⁒p4⁒δ0)pβˆ’1.

Proof.

If p=1, we let Ξ΅=1, resulting in Ξ΄=0 and ΞΈ=2, and we are done. If p>1, we choose Ξ΅ so that Ξ΄=Ξ΄0. Applying the Mean Value Theorem, we get

Ξ΅=(1+Ξ΄0)1/(pβˆ’1)βˆ’1β‰₯Ξ΄0β‹…mint∈(0,Ξ΄0)⁑(1+t)1/(pβˆ’1)βˆ’1pβˆ’1β‰₯45β‹…Ξ΄0pβˆ’1,

where we used that 1+t≀1+Ξ΄0≀5/4 and 1/(pβˆ’1)βˆ’1β‰₯βˆ’1. Therefore,

ΞΈ=2p⁒(1+1/Ξ΅)pβˆ’1≀2p⁒(5⁒(pβˆ’1)+4⁒δ04⁒δ0)pβˆ’1≀2p⁒(5⁒p4⁒δ0)pβˆ’1.

β—€

First, we establish the upper bound (4). We choose parameters according to Lemma 13 with Ξ΄0=m/(4⁒M). Then θ≀2p⁒(5⁒p⁒M/m)pβˆ’1. Since 0.5β‹…2p⁒(5⁒M⁒p/m)pβˆ’1β‰₯2pβˆ’1β‰₯1, we have

(1+2⁒θ)⁒M≀2.5β‹…2p⁒(5⁒M⁒pm)pβˆ’1β‹…Mmβ‹…m≀12⁒(10⁒M⁒pm)p⁒m.

We conclude that

𝔼⁒[ΞΎa⁒bβ‹…(costa⁒b⁑(w)βˆ’cost⁑(w))]≀m2⁒k⁒((10⁒M⁒pm)p⁒costβˆ—β‘(w)βˆ’cost⁑(w)).

Now we prove (5). We set Ξ΅=1; then ΞΈ=22⁒pβˆ’1 and Ξ΄=2pβˆ’1βˆ’1. From (12), we get

k⁒𝔼⁒[ΞΎa⁒bβ‹…(costa⁒b⁑(w)βˆ’cost⁑(w))]
≀(1+2⁒θ)⁒M⁒costβˆ—β‘(w)+2⁒δ⁒M⁒cost⁑(w)≀(1+22⁒p)⁒M⁒(cost⁑(w)+costβˆ—β‘(w))

Finally, for every swap caβ†’cbβˆ— in the support of π’Ÿ, we get the following upper bound from (11),

costa⁒b⁑(w)βˆ’cost⁑(w) β‰€βˆ‘u∈Vbβˆ—wu⁒(xuβˆ—pβˆ’xup)+βˆ‘u∈Vawu⁒(δ⁒xup+θ⁒xuβˆ—p)
β‰€βˆ‘u∈Xwu⁒xuβˆ—p+βˆ‘u∈Xwu⁒(δ⁒xup+θ⁒xuβˆ—p)≀(1+ΞΈ)⁒costβˆ—β‘(w)+δ⁒cost⁑(w).

Choosing Ξ΅ according to Lemma 13, we get the desired bound. β—€

5.5 Proof of Inequality 7

Applying Lemma 12, we get for α=10⁒M⁒p/m,

Ξ”i ≀m2⁒k⁒(Ξ±p⁒ziβˆ—βˆ’zi) (13)
Ξ”i ≀(1+22⁒p)⁒Mk⁒(zi+ziβˆ—). (14)

From Lemma 12, item 3, with δ0=1/(5⁒r) and

ΞΈ0=2p⁒(25⁒p⁒r4)pβˆ’1,

we get

z^i≀(1+ΞΈ0)⁒ziβˆ—+(1+Ξ΄0)⁒zi≀(1+15⁒r)⁒zi+(1+ΞΈ0)⁒ziβˆ—. (15)

Fix a threshold T=max⁑(5⁒r⁒(1+ΞΈ0)4, 2⁒(10⁒e⁒q)p)=O⁒(q)p. Consider two cases.

Current cost π’›π’Š is small: π’›π’Šβ‰€π‘»β’π’›π’Šβˆ—

From (15) and 1+ΞΈ0≀45⁒r⁒T,

z^i≀65⁒T⁒ziβˆ—+45⁒T⁒ziβˆ—=2⁒T⁒ziβˆ—.

Accordingly, when z^i>zi, M≀φ′⁒(z^i)=r⁒z^irβˆ’1≀r⁒(2⁒T⁒ziβˆ—)rβˆ’1. Also, m≀M. By (14)

Ξ”i ≀(4p+1)⁒Mk⁒(ziβˆ—+zi)=(4p+1)k⁒(Mβ‹…(ziβˆ—+zi+mM⁒zi)βˆ’mβ‹…zi)
≀(4p+1)k⁒((2⁒T+1)⁒M⁒ziβˆ—βˆ’m⁒zi)≀12⁒k⁒(4p+2β‹…rβ‹…(2⁒T)r⁒φ⁒(ziβˆ—)βˆ’Ο†β’(zi)).

Letting Ξ²=(2β‹…4p+2β‹…rβ‹…(2⁒T)r)1/q=O⁒(q), we get

Ξ”i≀14⁒k⁒(Ξ²q⁒φ⁒(ziβˆ—)βˆ’Ο†β’(zi)).
Current cost π’›π’Š is large: π’›π’Šβ‰₯π‘»β’π’›π’Šβˆ—

We show that 2⁒αp≀T. From (15) and 1+ΞΈ0≀45⁒r⁒T, we have

z^i≀(1+15⁒r+1+ΞΈ0T)⁒zi≀(1+1r)⁒zi.

Hence, when z^i>zi, M≀φ′⁒(z^i)=r⁒z^irβˆ’1≀e⁒r⁒zirβˆ’1 and α≀10⁒pβ‹…(M/m)≀10⁒pβ‹…(e⁒r)=10⁒e⁒q. Using that ziβ‰₯T⁒ziβˆ—β‰₯2⁒(10⁒e⁒q)p⁒ziβˆ—β‰₯2⁒αp⁒ziβˆ— and φ⁒(zi)=m⁒zi, we get from (13),

Ξ”i≀m2⁒k⁒(Ξ±p⁒ziβˆ—βˆ’zi)β‰€βˆ’m2⁒kβ‹…zi2=βˆ’14⁒k⁒φ⁒(zi).

6 Socially fair facility location

In this section, we consider two variants of the Socially Fair Facility Location problem and provide approximation algorithms for them.

We are given a set of n points X and a metric d on it, forming a metric space (X,d), as well as a set of possible facility locations F. There are β„“ groups on X represented by a weight function w:X→ℝβ‰₯0β„“ where wi⁒(u)β‰₯0 denotes the weight of client u in group i. Each facility c∈F is associated with a facility opening cost f⁒(c). We consider the following two settings with different types of facility opening costs: (1) group-homogeneous facility cost; (2) group-heterogeneous facility cost.

Group-homogeneous facility costs

Each facility c∈F has a scalar opening cost f⁒(c)β‰₯0, paid equally across groups. The objective is to choose CβŠ†F minimizing

FLhom(w,f,C):=(βˆ‘i=1β„“cost(wi,C)q/p)1/q+βˆ‘c∈Cf(c),

where cost⁑(wi,C)=βˆ‘u∈Xwi⁒(u)⁒d⁒(u,C)p.

[2] studied this objective with p=1 and q=∞ and gave a 4-approximation algorithm for it.

Group-heterogeneous facility costs

Each facility c∈F has a vector opening cost f⁒(c)βˆˆβ„β‰₯0β„“, where group i pays fi⁒(c) to open c.555We interpret fi⁒(c) as a group-specific fixed charge for opening facility c (e.g., taxes/subsidies or administrative overhead). Thus, group i pays fi⁒(c) whenever c is opened, regardless of whether any group-i client is assigned to c; this keeps opening costs dependent only on the opened set C, as in standard fixed-charge facility location.

In this case, the objective is666If the heterogeneous opening costs are group-uniform, i.e., fi⁒(c)=f⁒(c) for all i∈[β„“] and c∈F, then the objective becomes (βˆ‘i=1β„“(cost(C,wi)1/p+βˆ‘c∈Cf(c))q)1/q. We refer to this as the group-uniform cost variant. This objective is generally different from the group-homogeneous facility costs above. The two coincide when q=∞, but they differ for finite q. By using our heterogeneous convex relaxation with fi⁒(c)=f⁒(c) and applying the rounding scheme used for the homogeneous costs, we obtain an (8+Ξ΅)-approximation for this group-uniform cost variant.

FLhet(w,f,C):=(βˆ‘i=1β„“(cost(wi,C)1/p+βˆ‘c∈Cfi(c))q)1/q.

We get the following results for homogeneous and heterogeneous facility costs.

See 5 See 6

We now provide the approximation algorithm for the group-heterogeneous setting.

Proof of Theorem 6.

We use a relaxation of the problem and then use a randomized rounding procedure to get an integer solution. We consider the following relaxation

min H
s.t. βˆ‘i=1β„“zi≀Hq
ziβ‰₯(βˆ‘uwi⁒(u)β’βˆ‘c∈Fd⁒(u,c)pβ‹…xu,c)qp βˆ€i∈[β„“] (16)
ziβ‰₯(βˆ‘c∈Fycβ‹…fi⁒(c))q βˆ€i∈[β„“] (17)
ziβ‰₯βˆ‘c∈Fycβ‹…fi⁒(c)q βˆ€i∈[β„“] (18)
βˆ‘c∈Fxu,cβ‰₯1 βˆ€u∈X (19)
xu,c≀yc βˆ€u∈X,βˆ€c∈F
0≀yc≀1 βˆ€c∈F
0≀xu,c≀1 βˆ€u∈X,βˆ€c∈F

We can binary search on H. For any fixed value of H, the relaxation above is convex.

We then apply the following randomized rounding algorithm inspired by [19, 24]. Let (xβˆ—,yβˆ—,zβˆ—,Hβˆ—) denote the fractional solution to the convex program above. The key difference is that, instead of opening the cheapest facility in Bu, we open exactly one facility cu in Bu selected randomly with probability proportional to ycβˆ—. For each point u∈X, let Au=βˆ‘c∈Fd⁒(u,c)p⁒xu,cβˆ— denote the connection cost of point u given by the fractional solution. Then, we sort all points in X by their connection costs in increasing order. We iteratively perform the following steps until all points are assigned to open facilities. We first pick the unassigned point u with the smallest connection cost Au as an anchor point. Let Bu={c∈F:d⁒(u,c)p≀2⁒Au} be all facilities in a ball with radius (2⁒Au)1/p centered at u. It can be shown that the balls corresponding to distinct anchor points are disjoint. Then, we sample exactly one facility cu in Bu with probability proportional to ycβˆ—. Assign all unassigned points v with distance d⁒(v,u)≀(2⁒Au)1/p+(2⁒Av)1/p to this new facility cu. Let C^ be the set of centers sampled by the rounding algorithm.

We now analyze the cost of this integer solution given by the rounding algorithm. Let y^c∈{0,1} be the indicator variable to denote whether facility c is selected in C^. We first analyze the facility opening cost of this solution. By a simple averaging argument, for each iteration with anchor node u, we have βˆ‘c∈Buycβˆ—β‰₯1/2. Since we open exactly one facility cu in Bu with probability proportional to ycβˆ—, we have, for each facility c∈Bu,

𝔼⁒[y^c]=ycβˆ—βˆ‘c∈Buycβˆ—β‰€2⁒ycβˆ—.

Consider any fixed group i. For each iteration with anchor point u, we define a random variable Yu=βˆ‘c∈Buy^c⁒fi⁒(c) which represents the contribution to the facility cost of group i from that iteration. Since the choices made in distinct, disjoint anchor balls are independent, the collection {Yu} forms a set of independent non-negative random variables. By the Rosenthal inequality (see [18]), we have

𝔼⁒[(βˆ‘uYu)q]1/q≀O⁒(qlog⁑q)⁒max⁑{(βˆ‘u𝔼⁒[Yuq])1/q,βˆ‘u𝔼⁒[Yu]}.

Note that in each iteration, exactly one facility cu in Bu is opened, which means exactly one random variable y^cu=1 and all other y^c=0 in Bu. Thus, we have

𝔼⁒[Yuq]=𝔼⁒[(βˆ‘c∈Buy^cβ‹…fi⁒(c))q]=𝔼⁒[βˆ‘c∈Buy^cβ‹…fi⁒(c)q]≀2β’βˆ‘c∈Buycβˆ—β‹…fi⁒(c)q.

Hence, we have βˆ‘u𝔼⁒[Yuq]≀2β’βˆ‘cβˆˆβ‹ƒuBuycβˆ—β‹…fi⁒(c)q≀2⁒ziβˆ—. We also have

βˆ‘u𝔼⁒[Yu]=βˆ‘cβˆˆβ‹ƒuBufi⁒(c)⁒𝔼⁒[y^c]≀2β’βˆ‘cβˆˆβ‹ƒuBufi⁒(c)⁒ycβˆ—β‰€2⁒(ziβˆ—)1/q≀O⁒(qlog⁑q)⁒Hβˆ—.

Therefore, we have

𝔼⁒[(βˆ‘cβˆˆβ‹ƒuBuy^c⁒fi⁒(c))q]≀O⁒((2⁒qlog⁑q)q)⁒ziβˆ—.

By taking the sum over all groups and applying Markov’s inequality, with probability at least 1/2, we have

βˆ‘i=1β„“(βˆ‘cβˆˆβ‹ƒuBuy^c⁒fi⁒(c))q≀O⁒((2⁒qlog⁑q)q)β’βˆ‘i=1β„“ziβˆ—β‰€O⁒((2⁒qlog⁑q)q)⁒(Hβˆ—)q

We then analyze the connection cost of this integer solution. If v is assigned when u is the anchor, then Au≀Av and d⁒(v,cu)≀d⁒(v,u)+d⁒(u,cu)≀3⁒(2⁒Av)1/p. Hence, the connection cost for each group i given by C^ is at most

cost(wi,C^)1/p=(βˆ‘u∈Xwi(u)β‹…d(u,C^)p)1/p≀(3pβ‹…2βˆ‘u∈Xwi(u)β‹…Au)1/p≀6(ziβˆ—)1/q.

By combining with the facility opening cost, the facility location cost is at most

(βˆ‘i=1β„“(cost(wi,C^)1/p+βˆ‘c∈C^fi(c))q)1/q
≀ (βˆ‘i=1β„“2qcost(wi,C^)q/p+2q(βˆ‘c∈C^fi(c))q)1/q≀O(qlog⁑q)β‹…Hβˆ—.

Therefore, by computing a (1+Ξ΅)-approximate solution to the convex relaxation, this randomized rounding provides the desired approximation with probability at least 1/2. β—€

References

  • [1] Fateme Abbasi, Sandip Banerjee, JarosΕ‚aw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, DΓ‘niel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized approximation schemes for clustering with general norm objectives. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 1377–1399, 2023. doi:10.1109/FOCS57990.2023.00085.
  • [2] Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equitable group representations. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 504–514, 2021. doi:10.1145/3442188.3445913.
  • [3] Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Benjamin Moseley, Philip Pham, Sergei Vassilvitskii, and Yuyan Wang. Fair hierarchical clustering. Advances in Neural Information Processing Systems, 33:21050–21060, 2020.
  • [4] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 267–275, 2019. doi:10.1145/3292500.3330987.
  • [5] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844–856, 1995. doi:10.1145/210332.210337.
  • [6] Barbara Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems. Mathematics of Operations Research, 35(1):79–101, 2010. doi:10.1287/MOOR.1090.0428.
  • [7] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544–562, 2004. doi:10.1137/S0097539702416402.
  • [8] Sayan Bandyapadhyay, Tianzhi Chen, Zachary Friggstad, and Mahya Jamshidian. A constant-factor approximation for pairwise fair k-center clustering. In International Conference on Integer Programming and Combinatorial Optimization, pages 43–57. Springer, 2025. doi:10.1007/978-3-031-93112-3_4.
  • [9] Sayan Bandyapadhyay, Eden ChlamtÑč, Zachary Friggstad, Mahya Jamshidian, Yury Makarychev, and Ali Vakilian. A polynomial-time approximation for pairwise fair k-median clustering. In The 29th International Conference on Artificial Intelligence and Statistics, 2026.
  • [10] Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann. New approximability results for the robust k-median problem. In Scandinavian Workshop on Algorithm Theory, pages 50–61. Springer, 2014. doi:10.1007/978-3-319-08404-6_5.
  • [11] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. Advances in neural information processing systems, 30, 2017.
  • [12] Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and MichaΕ‚ Pilipczuk. Designing fpt algorithms for cut problems using randomized contractions. SIAM Journal on Computing, 45(4):1171–1229, 2016. doi:10.1137/15M1032077.
  • [13] Eden ChlamtÑč, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In Proceedings of the Symposium on Discrete Algorithms (SODA), pages 2664–2683, 2022. doi:10.1137/1.9781611977073.104.
  • [14] Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair k-means clustering. In Proceedings of the ACM Conference on Fairness, Accountability, and Transparency, pages 438–448, 2021. doi:10.1145/3442188.3445906.
  • [15] Mehrdad Ghadiri, Mohit Singh, and Santosh S Vempala. Constant-factor approximation algorithms for socially fair k-clustering. arXiv preprint arXiv:2206.11210, 2022. doi:10.48550/arXiv.2206.11210.
  • [16] Dishant Goyal and Ragesh Jaiswal. Tight fpt approximation for socially fair clustering. Information Processing Letters, 182:106383, 2023. doi:10.1016/J.IPL.2023.106383.
  • [17] Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location. arXiv preprint arXiv:0809.2554, 2008. arXiv:0809.2554.
  • [18] William B Johnson, Gideon Schechtman, and Joel Zinn. Best constants in moment inequalities for linear combinations of independent and exchangeable random variables. The Annals of Probability, pages 234–253, 1985.
  • [19] Adam Kasperski, Adam Kurpisz, and PaweΕ‚ ZieliΕ„ski. Approximability of the robust representatives selection problem. Operations Research Letters, 43(1):16–19, 2015. doi:10.1016/J.ORL.2014.10.007.
  • [20] Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering. In International conference on machine learning, pages 6586–6596. PMLR, 2020. URL: http://proceedings.mlr.press/v119/mahabadi20a.html.
  • [21] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of johnson–lindenstrauss transform for k-means and k-medians clustering. SIAM Journal on Computing, 52(2):269–297, 2022.
  • [22] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory, pages 3246–3264. PMLR, 2021. URL: http://proceedings.mlr.press/v134/makarychev21a.html.
  • [23] David B Shmoys, Γ‰va Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In Proceedings of the Symposium on Theory of Computing, pages 265–274, 1997.
  • [24] Aravind Srinivasan. Approximation algorithms via randomized rounding: a survey. Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN, pages 9–71, 1999.