Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints

Bandyapadhyay, Sayan; Chen, Tianzhi

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.23

Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints

Sayan Bandyapadhyay

Portland State University, OR, USA Tianzhi Chen

Portland State University, OR, USA

Abstract

In this work, we study $k$ -min-sum-of-radii ( $k$ -MSR) clustering under mergeable constraints. $k$ -MSR seeks to group data points using a set of up to $k$ balls, such that the sum of the radii of the balls is minimized. A clustering constraint is called mergeable if merging two clusters satisfying the constraint, results in a cluster that also satisfies the constraint. Many popularly studied constraints are mergeable, including fairness constraints and lower bound constraints.

In our work, we design a $(4+\epsilon)$ -approximation for $k$ -MSR under any given mergeable constraint with runtime $2^{O(\frac{k}{\epsilon}\cdot\log^{2}\frac{k}{\epsilon})}n^{4}$ , i.e., fixed-parameter tractable in $k$ for constant $\epsilon$ . Our result directly improves upon the FPT $(6+\epsilon)$ -approximation by Carta et al. [10]. We also provide a hardness result that excludes the exact solvability of $k$ -MSR under any given mergeable constraint in time $f(k)n^{o(k)}$ , assuming ETH is true.

Keywords and phrases:

sum-of-radii clustering, mergeable constraints, approximation algorithm

Category:

APPROX

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis

Funding:

This work was supported by the National Science Foundation under Grant No. AF 2311397.

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.23

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Given a set of points in a metric space and an integer $k>0$ , the $k$ -min-sum-of-radii clustering problem ( $k$ -MSR for short) seeks to group the points using a set of at most $k$ balls, called clusters, each centered at a point, minimizing the sum of the radii of those balls. Like most clustering objectives, finding an optimal $k$ -MSR clustering is NP-hard, as shown by Gibson et al. [21]. They also designed a quasi-polynomial-time approximation scheme (QPTAS) for $k$ -MSR in the same work, implying it is unlikely that $k$ -MSR is APX-hard under standard complexity-theoretic assumptions. Consequently, substantial attention has been directed toward designing approximation algorithms. Currently, the best-known polynomial-time approximation factor is $3+\epsilon$ [9].

To highlight the motivation for studying $k$ -MSR, we compare it to $k$ -center and $k$ -median, two popular clustering objectives. $k$ -center is similar to $k$ -MSR, but instead of minimizing the sum of the radii of balls, it minimizes the radius of the largest ball. Simple $2$ -approximation algorithms exist for $k$ -center [22, 23], and variants of $k$ -center are relatively easy to solve. However, as a trade-off, $k$ -center is prone to outliers, as well as artifacts such as the dissection effect shown in Figure 1, where clusters might be split unnecessarily. $k$ -median, on the other hand, seeks to minimize the sum of each point’s distance to the closest center, rather than the radii of a cluster. $k$ -median and its variants are relatively more difficult to solve, but its robustness has given rise to its popularity [3, 16]. Informally, the $k$ -MSR problem lies between $k$ -center and $k$ -median – it reduces the dissection effect seen in $k$ -center, while often allowing for simpler solutions than those typically admitted by $k$ -median, which motivates our study.

$k$ -MSR clustering has also been studied under additional constraints, popularly known as constrained variants. In our work, we focus on specific types of constraints, namely mergeable constraints. A clustering constraint is said to be mergeable if merging two clusters that satisfy the constraint, results in a cluster that also satisfies the constraint. The property has proven useful for analyzing constrained $k$ -MSR clustering, with a number of works dedicated to it [10, 18, 6]. A popular class of mergeable constraints includes many fairness constraints. First introduced by Chierichetti et al. [15], given a partition of the input dataset into groups based on some attribute (commonly referred to as colors), fair clustering aims to ensure that each group in the dataset is proportionally represented within every cluster. For instance, given a set of red and blue points, fair clustering seeks to have a balanced number of red and blue points in each cluster. Carta et al. showed that many common fairness constraints are mergeable [10]; we discuss these constraints further in Section 1.2. There are also non-fair constraints that are mergeable, such as the lower bound constraint, where each cluster is required to have at least $L$ points, for some given $L>0$ [1].

Constrained versions of $k$ -MSR are often difficult to approximate and lack tractability in polynomial time. A potential approach to address this issue is the design of fixed-parameter tractable (FPT) algorithms. FPT algorithms still have a runtime polynomial in the input size but do not have to be polynomial in their parameters. For example, an algorithm running in $O(n^{2}\cdot 2^{k})$ time is considered to be FPT in parameter $k$ . Fixed-parameter tractability essentially allows efficient computation, assuming the parameters are small in practice. For challenging constrained clustering problems such as constrained $k$ -MSR, FPT algorithms are often the preferred approach, as they offer computational tractability and can yield improved approximation guarantees. In our work, we also adopt this approach to address the complexity of the problem.

1.1 Our Contributions

Our work establishes two main results concerning $k$ -MSR under mergeable constraints: one demonstrating that the problem admits a $(4+\epsilon)$ -approximation in FPT time in $k$ for constant $\epsilon$ , and another proving its computational hardness. We begin by presenting the following theorem.

Theorem 1.

For any $\epsilon>0$ , there is a $(4+\epsilon)$ -approximation algorithm for the $k$ -MSR problem under mergeable constraints that runs in $2^{O(\frac{k}{\epsilon}\cdot\log^{2}\frac{k}{\epsilon})}n^{4}$ time.

Our result directly improves upon the FPT $(6+\epsilon)$ -approximation by Carta et al. [10]. Moreover, to solve $k$ -MSR under a given mergeable constraint, their algorithm requires the existence of a constant-factor approximation algorithm for $k$ -center under the same constraint, while ours does not have this restriction. There are constraints under which no constant-factor approximation is known for $k$ -center. For instance, no approximation algorithm is known for $k$ -center under what is called fair representational constraint, which is one of the more general definitions of fair constraints. Our algorithm also has the advantage of generality. While the FPT algorithms by Drexler et al. [18] and Banerjee et al. [6] achieve an approximation factor of $(1+\epsilon)$ , they are limited to specific metric spaces such as Euclidean spaces or those with bounded doubling dimension. In contrast, our algorithm applies to general metric spaces.

Next, we give the following theorem regarding the hardness of $k$ -MSR clustering under the fair representational constraint.

Theorem 2.

Fair Representational Clustering cannot be solved in time $f(k)n^{o(k)}$ unless ETH is false.

This result also trivially extends to $k$ -MSR under mergeable constraints, as the fair representational constraint is known to be mergeable [18].

1.2 Related Work

Gibson et al. showed that the $k$ -MSR objective is NP-hard, even in planar graphs and metrics with doubling dimensions [21]; consequently, a line of work gave approximation algorithms for the problem. Charikar and Panigrahy first gave a polynomial time $3.504$ -approximation for the problem in their seminal work [12]. This result remained the best approximation until Friggstad and Jamshidian followed up with a $3.489$ -approximation nearly twenty years later [20]. Soon after, Buchem et al. improved the approximation factor to $(3+\epsilon)$ , which is the current best known in polynomial time [9].

$k$ -MSR has been studied under various constraints, most notably the capacitated constraint and the matroid constraint. A line of work on devising $O(1)$ -approximation for capacitated $k$ -MSR led to an FPT $3$ -approximation [24, 19, 25, 5]. $k$ -MSR has also been studied under matroid constraints, leading to an FPT $(9+\epsilon)$ approximation by Inamdar and Varadarajan [24] and an improved $(3+\epsilon)$ approximation by Chen et al. [13]. Polynomial time $O(1)$ -approximations for these variants of $k$ -MSR are not known. Interestingly, polynomial time $O(1)$ -approximations exist for $k$ -MSR with lower bound [2, 9].

Another common $k$ -MSR constraint to study is the mergeable constraint. Most of the studies are geared towards fairness constraints, since many fairness constraints are mergeable. Drexler et al. first developed an FPT $(1+\epsilon)$ -approximation algorithm for $k$ -MSR under mergeable constraints in Euclidean metrics of arbitrary dimension with constant $k$ [18]. The result was subsequently extended to metrics with bounded doubling dimension by Banerjee et al. [6]. Carta et al. gave a $(6+\epsilon)$ -approximation algorithm for $k$ -MSR under mergeable constraints in general metrics [10].

Fair $k$ -MSR has also received attention from researchers. Carta et al. showed that several fairness constraints are mergeable [10]. We name a few of these constraints that are commonly used. The simplest definition is called exact fairness [8], where each cluster must have exactly the same number of points from each color. The next step up is Pairwise Fair Clustering (or sometimes called $(t,k)$ -fair clustering) [15]. Given a set of red points and blue points and integer $t>0$ , Pairwise Fair Clustering ensures that the ratio between blue and red points in each cluster is between $t$ and $\frac{1}{t}$ . This definition is sometimes extended to have more than two colors. Another common fairness definition is called Fair Representational Clustering [7, 8], where the fraction of points in some color $i$ allowed in each cluster is at most $\alpha_{i}$ and at least $\beta_{i}$ , given parameters $\alpha_{i},\beta_{i}\in[0,1]$ . Bandyapadhyay et al. gave polynomial-time $O(1)$ -approximation algorithms for $k$ -MSR under the Pairwise Fair Clustering constraint with two groups and exact fair constraint for $l\geq 2$ groups [4]. Chen et al. developed an FPT $(3+\epsilon)$ -approximation algorithm for $k$ -MSR under an alternate notion of fairness that is a special case of matroid $k$ -MSR [13]. In their definition of fairness, each color is allowed to have a pre-defined number $k_{i}$ of points that can be chosen as cluster centers. Banerjee et al. [6] also gave an FPT $(1+\epsilon)$ -approximation algorithm for the same problem in Euclidean metric. For more works on fair clustering, one can refer to the survey by Chhabra et al. [14].

Roadmap.

We first define some notations in Section 2, then describe our algorithm in Section 3, and finally prove our hardness result in Section 4.

2 Preliminaries

In $k$ -MSR clustering, we are given a set $P$ of $n$ points in a metric space with metric $d$ . The goal is to find (i) a set of up to $k$ points $C=\{c_{1},\dots,c_{k}\}\subset P$ called centers, and (ii) a function $\phi$ assigning each point $p\in P$ to some center $c_{i}\in C$ . We call $(C,\phi)$ a clustering of $P$ . For each $c_{i}\in C$ , we call $\mathcal{C}_{i}=\phi^{-1}(c_{i})$ the cluster centered at $c_{i}$ , and we define the radius corresponding to $c_{i}$ as $r_{i}=\max_{p:\phi(p)=c_{i}}d(p,c_{i})$ . We refer to the sum of radii of a clustering $(C,\phi)$ as the cost of the clustering, and we denote it by $\text{cost}(C,\phi)$ ; we use the same notation $\text{cost}(R)$ to denote a sum of a set of radii $R$ , or $\text{cost}(\mathcal{C})$ for a set of clusters $\mathcal{C}$ .

We merge two clusters $C_{i}=\phi^{-1}(c_{i}),C_{j}=\phi^{-1}(c_{j})$ by setting $\phi(p)=c$ for all points $p\in C_{i}\cup C_{j}$ and some $c\in P$ . We say that a constraint is mergeable if for any two clusters satisfying the constraint, merging the clusters results in a new cluster that also satisfies the constraint. We refer to a clustering that satisfies some (mergeable) constraint as a constrained clustering, and a clustering without any constraint as a vanilla clustering. We say that a clustering $(C,\phi)$ is feasible if every point in $P$ is assigned to some center, $|C|\leq k$ , and each cluster satisfies the desired constraint (if any). Moreover, we say that a clustering $(C,\phi)$ is optimal if it is feasible, and $\text{cost}(C,\phi)$ is minimized over all such clustering.

We denote a ball with center $c$ and radius $r$ by $B(c,r)$ . Given a point $p$ and a ball $B(c,r)$ , we say that $p$ is contained in $B(c,r)$ if $d(p,c)\leq r$ , denoted by $p\in B(c,r)$ ; note that a point $p$ may be contained in a ball $B(c,r)$ , but not assigned to its center $c$ , as $p$ may be contained in multiple balls but only assigned to one cluster.

3 An FPT $(4+\epsilon)$ -approximation Algorithm

In this section, we describe an FPT $(4+\epsilon)$ -approximation algorithm for $k$ -MSR under mergeable constraints. We first describe the algorithm at a high level, then state the procedures that it calls, present the algorithm, and lastly analyze it.

Our algorithm stems from the idea that we can find a vanilla clustering and expand the balls such that each cluster of any constrained clustering is contained within one of the expanded balls. This allows us to transform a vanilla clustering into a constrained clustering in FPT time in $k$ . Our algorithm has four major steps: (1) Guess the radii of an optimal vanilla clustering up to a $(1+\epsilon)$ factor. (2) Compute a $(2+\epsilon)$ -approximate vanilla clustering using the guessed radii, (3) Expand the vanilla clusters, resulting in a $(3+\epsilon)$ -approximate set of balls, and (4) Merge the expanded balls to create clusters that satisfy the given mergeable constraint. These steps are accomplished through calls to a series of procedures, which we describe in the following subsections.

Similar to our algorithm, the algorithm of Carta et al. [10] also finds a $(3+\epsilon)$ -approximate set of balls with the aforementioned containment property. However, our algorithm finds the balls in a simpler and more general manner in that it does not rely on a $k$ -center algorithm under the same constraint to obtain the balls. Carta et al. also made the same observation as ours that one can satisfy the mergeable constraint by merging the $(3+\epsilon)$ -approximate balls, but our approach differs in how we choose the new center for each set of balls being merged. The algorithm of Carta et al. picks the center of the largest ball, which results in a $2$ factor increase in cost, but we show that one can always pick a center that results in at most a $\frac{4}{3}$ factor increase in cost.

3.1 Finding a Vanilla Clustering

We first describe a procedure that takes a radii vector $(r_{1},\dots,r_{l})$ , and a multiplicity vector $(k_{1},\dots,k_{l})$ as input. Moreover, if there is a feasible vanilla clustering that uses those radii with the respective multiplicities, the procedure outputs a vanilla clustering that uses those radii values up to a factor of 2 with the same multiplicities. We make use of the fact shown in Observation 3 that for any point $p$ in a cluster $\mathcal{C}_{i}$ with radius $r_{i}$ , we can cover all points in the cluster with a ball centered at $p$ with a radius of $2\cdot r_{i}$ . This allows us to recursively find a point $p$ that is not yet covered, and guess the cluster containing $p$ and the corresponding radius to cover all points of that cluster. We note that our procedure is essentially the same as the procedure used by Chen et al. in their work on $k$ -MSR [13], but restated to take in a pair of radii and multiplicity vectors as an additional input; this allows us to use the same set of radii and multiplicity vectors in both the vanilla clustering step and the cluster expansion step of our algorithm. The procedure is given as Algorithm 1.

Algorithm 1 Vanilla-Clustering

(P,R_{i},K_{i})

.

Observation 3.

For any cluster $\mathcal{C}_{i}$ with center $c$ and radius $r$ , we can cover all points in $\mathcal{C}_{i}$ using a ball centered at some point $p\in C$ with radius $2\cdot r$ .

Proof.

Consider the point $p$ and some other point $p^{\prime}\in\mathcal{C}_{i}$ . By triangle inequality, we have that $d(p,p^{\prime})\leq d(p,c)+d(p^{\prime},c)$ . Furthermore, since $p,p^{\prime}\in\mathcal{C}_{i}$ , $d(p,c),d(p^{\prime},c)\leq r$ . It follows that $d(p,p^{\prime})\leq 2\cdot r$ for any $p,p^{\prime}\in\mathcal{C}_{i}$ , therefore we can cover all points in $C$ with any point $p\in\mathcal{C}_{i}$ and a radius $2\cdot r$ . $\hfill\blacktriangleleft$

Lemma 4.

Suppose there is a feasible vanilla clustering of $P$ that uses exactly $k_{j}$ balls of radius $r_{j}$ for $1\leq j\leq l$ . Then Algorithm 1 outputs a feasible vanilla clustering of $P$ that uses at most $k_{j}$ balls of radius $2\cdot r_{j}$ for $1\leq j\leq l$ .

Proof.

Let $\mathcal{C}^{*}=\{\mathcal{C}^{*}_{1},\dots,\mathcal{C}^{*}_{k}\}$ be a set of feasible vanilla clusters corresponding to the radii vector $R_{i}$ . We consider the following construction of $(C_{v},\phi_{v})$ . Let $p$ be some point in $P$ . Note that $p$ is in some $\mathcal{C}^{*}_{i}\in\mathcal{C}^{*}$ with radius $r_{j}$ for some $j$ . We add $p$ to $C_{v}$ as a new center and set $\phi_{v}(q)=p$ for all points $q$ such that $d(p,q)\leq 2\cdot r_{j}$ , and remove $p$ and all such $q$ from $P$ . We also remove the cluster $\mathcal{C}^{*}_{i}$ from consideration. We can do this because by Observation 3 we have that $p$ with a radius of $2\cdot r_{j}$ covers all points in $\mathcal{C}^{*}_{i}$ . We repeat this process until there are no points left in $P$ . We can always find a clustering within $k$ iterations this way because each time we repeat the process, we cover all points in some cluster $\mathcal{C}^{*}_{i}$ . Specifically, there exists a recursion branch in Algorithm 1 that follows this construction. It follows that Algorithm 1 outputs the desired vanilla clustering of $P$ . $\hfill\blacktriangleleft$

Lemma 5.

Given a vector $R_{i}$ with $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ radii, Algorithm 1 runs in $(O(\log_{1+\epsilon}\frac{k}{\epsilon}))^{k}n$ time.

Proof.

First, we consider the depth of the recursive calls in Algorithm 1. Since each clustering is restricted to having a maximum of $k$ clusters, and each recursive call decreases the number of clusters by one, each branch of recursive calls will have at most $k$ levels of recursion. Now, we consider how many additional calls each recursive call makes. By our assumption, we have $O(\log_{1+\epsilon}(\frac{k}{\epsilon}))$ radii in $R_{i}$ . Since each recursive call makes an additional call for each $r_{j}\in R_{i}$ with $k_{j}>0$ , each recursive call can make $O(\log_{1+\epsilon}(\frac{k}{\epsilon}))$ additional calls. Since each call can be computed in $O(n+k)$ time, it follows that Algorithm 1 runs in $(O(\log_{1+\epsilon}\frac{k}{\epsilon}))^{k}n$ time. $\hfill\blacktriangleleft$

3.2 Expanding the Vanilla Clustering

Given a feasible vanilla clustering, we describe a process to expand the vanilla balls so that each cluster of a fixed, constrained clustering is contained in one of the expanded balls. The idea is to guess how much to expand the vanilla clusters using a guessed set of radii for the constrained clustering. In particular, for each vanilla cluster $\mathcal{C}_{v}^{i}$ , we guess the biggest constrained cluster whose center is contained in $\mathcal{C}_{v}^{i}$ , and expand $\mathcal{C}_{v}^{i}$ by its radius, thereby fully containing all the constrained clusters whose centers are in $\mathcal{C}_{v}^{i}$ . We assume that the radii vector $R_{i}=(r_{1},\dots,r_{l})$ and a multiplicity vector $K_{i}=(k_{1},\dots,k_{l})$ of the constrained clustering are given. The procedure is given as Algorithm 2.

Algorithm 2 Expand-Balls

(C_{v},\phi_{v},R_{i},K_{i})

.

Now we show some properties of the output of Algorithm 2.

Lemma 6.

Given a vanilla clustering with balls $B_{1}(c_{1},r_{1}^{v}),\ldots,B_{k}(c_{k},r_{k}^{v})$ , and the radii vector $R_{i}=(r_{1},\dots,r_{l})$ and a multiplicity vector $K_{i}=(k_{1},\dots,k_{l})$ of a fixed constrained clustering, the output $R_{e}$ of Algorithm 2 contains a vector $(r_{1}^{c},\dots,r_{k}^{c})$ such that each cluster of the constrained clustering is contained in $B(c_{j},r_{j}^{c})$ for some $1\leq j\leq k$ . Moreover, $\sum_{j=1}^{k}r_{j}^{c}\leq\sum_{j=1}^{k}r_{j}^{c}+\sum_{t=1}^{l}k_{t}\cdot r_% {t}$ .

Proof.

Let $\mathcal{C}^{*}=\{\mathcal{C}^{*}_{1},\dots,\mathcal{C}^{*}_{k}\}$ be a fixed constrained clustering that for each $1\leq t\leq l$ uses $k_{t}$ clusters of radii $r_{t}$ . Consider the following construction of a vector $(r_{1}^{c},\dots,r_{k}^{c})$ . For each center $c_{j}\in C_{v}$ with radius $r_{j}^{v}$ , let $\mathcal{C}^{*}_{\psi(j)}$ be the largest cluster in $\mathcal{C}^{*}$ whose center is in the vanilla cluster $\mathcal{C}_{v}^{j}$ , and let $r_{\psi(j)}^{*}$ be its radius. We set each $r_{j}^{c}$ to $r_{j}^{v}+r_{\psi(j)}^{*}$ . Note that the expanded ball $B(c_{j},r_{j}^{c})$ contains any cluster in $\mathcal{C}^{*}$ whose center is in $\mathcal{C}_{v}^{j}$ , satisfying the desired property. As the center of each constrained cluster in $\mathcal{C}^{*}$ is contained in a unique vanilla cluster, the radius of the constrained cluster is used at most once to expand the radius of that vanilla cluster. In particular, each $r_{t}\in R_{i}$ is used at most $k_{t}$ times for the expansion. It follows that $(r_{1}^{c},\dots,r_{k}^{c})$ is in $R_{e}$ . For the same reason, $\sum_{j=1}^{k}r_{j}^{c}=\sum_{j=1}^{k}(r_{j}^{v}+r_{\psi(j)}^{*})\leq\sum_{j=1% }^{k}r_{j}^{v}+\sum_{t=1}^{l}k_{t}\cdot r_{t}$ , which proves the moreover part. $\hfill\blacktriangleleft$

Now we show the following two lemmas about the output size and runtime of Algorithm 2.

Lemma 7.

Given the vectors $R_{i},K_{i}$ of size $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ , the number of guesses $|R_{e}|$ that Algorithm 2 outputs is bounded by $(O(\log_{1+\epsilon}\frac{k}{\epsilon}))^{k}$ .

Proof.

Algorithm 2 computes $R_{e}$ by enumerating a set of guesses $E$ for how much to expand each vanilla cluster. There are $k$ vanilla clusters, and there are $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ ways to expand each cluster, since there are $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ distinct radii in $R_{i}$ . It follows that the number of entries in $E$ and $R_{e}$ are bounded by $(O(\log_{1+\epsilon}\frac{k}{\epsilon}))^{k}$ . $\hfill\blacktriangleleft$

Since each entry in $E$ takes $O(k)$ time to compute, we have the following lemma.

Lemma 8.

Given the vectors $R_{i},K_{i}$ of size $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ , Algorithm 2 runs in $(O(\log_{1+\epsilon}\frac{k}{\epsilon}))^{k}$ time.

3.3 Merging Balls

Suppose we are given a set of balls that cover a set of points $P$ . Moreover, we assume that there is a clustering of $P$ with a mergeable constraint such that each cluster is contained in one of the given balls. We design a procedure that helps find a clustering of $P$ with the mergeable constraint such that its cost is at most $4/3$ times the sum of the radii of the given balls.

Before describing the algorithm, we define a few notations. Let $B=\{B_{1},\dots,B_{k}\}$ denote a set of balls. Let $G=(B,E)$ be a graph with the balls in $B$ as vertices and the set of edges $E=\{(B_{i},B_{j})\mid B_{i},B_{j}\in B\text{ and there is a point such that }p% \in B_{i}\text{ and }p\in B_{j}\}$ . A connected component of $G$ therefore contains a maximal subset of balls where every pair is connected by a path.

The merging algorithm, Algorithm 3, is quite simple. Given a set of balls $B$ that cover a set of points $P$ , Algorithm 3 first construct the graph $G=(B,E)$ as defined above. For each connected component of balls $B^{\prime}$ in $G$ , Algorithm 3 finds a point $c$ contained in the balls of $B^{\prime}$ such that assigning all other points contained in $B^{\prime}$ to $c$ results in a cluster whose radius is minimized.

Algorithm 3 Merge-Balls

(B)

.

In the following, we show that the output clustering $(C,\phi)$ of Algorithm 3 satisfies a mergeable constraint based on an additional assumption.

Lemma 9.

Suppose there is a clustering $\mathcal{C}$ of $P$ with a mergeable constraint such that each cluster is contained in a ball of $B$ . Then the output clustering $(C,\phi)$ of Algorithm 3 satisfies the mergeable constraint.

Proof.

Since each cluster in $\mathcal{C}$ is in a ball of $B$ , the union of the balls in each connected component of $G$ is the disjoint union of a subset of clusters of $\mathcal{C}$ . This means that when Algorithm 3 merges the balls in a connected component into a single cluster, the resulting cluster satisfies the constraint, as the constraint is mergeable. It follows that the output clustering $(C,\phi)$ also satisfies the mergeable constraint. $\hfill\blacktriangleleft$

Lemma 10.

Algorithm 3 runs in $O(kn^{2})$ time.

Proof.

The main bottlenecks of Algorithm 3 are the construction of the edges $E$ for graph $G$ , and finding a center $c$ in each connected component $B^{\prime}$ that minimizes the radius when merging the balls in $B^{\prime}$ . Since there are $O(n)$ points in $P$ and $O(k)$ balls, checking if each point $p\in P$ is in both of each pair of $B_{i},B_{j}$ to construct $E$ takes $O(nk^{2})$ time. To find $c$ , we can simply probe all points in the connected component. Since there are $O(k)$ components, and each component can contain up to $O(n)$ points, we can find $c$ in $O(kn^{2})$ time, resulting in an overall runtime of $O(kn^{2})$ . $\hfill\blacktriangleleft$

Next, we give an upper bound on the cost of the clustering $(C,\phi)$ computed by Algorithm 3. Consider any connected component of $G$ with a set of balls $B^{\prime}$ . Let $P^{\prime}$ be the set of points in the union of the balls of $B^{\prime}$ . Denote the sum of the radii of the balls in $B^{\prime}$ by $\mathcal{R}$ . Then we have the following lemma.

Lemma 11.

There is a point $c\in P^{\prime}$ such that for any $q\in P^{\prime}$ , $d(p,q)\leq\frac{4}{3}\mathcal{R}$ .

Before proving the lemma, we describe a major consequence of it. Recall that for each connected component of $G$ , Algorithm 3 assigns all points in the associated balls to a single cluster center $c$ . Moreover, this center $c$ is chosen to be a point ${p}\in P^{\prime}$ that minimizes the maximum distance from all other points. Thus, by the above lemma, the resulting cluster $\mathcal{C}=\phi^{-1}(c)$ has $\text{cost}(\mathcal{C})\leq\frac{4}{3}\mathcal{R}$ , where $\mathcal{R}$ is the sum of the radii of the balls in the component. As $B$ is the disjoint union of balls in the components, we have the following corollary.

Corollary 12.

The cost of the output clustering $(C,\phi)$ of Algorithm 3 is at most $\frac{4}{3}$ times the sum of the radii of the input balls in $B$ .

Now, we move on towards proving Lemma 11. We need a few additional definitions and observations. Let $T$ be a spanning tree of the concerned connected component. We call a path $\pi=\{\pi_{1},\dots,\pi_{m}\}$ in $T$ a maximum leaf-to-leaf path if $\pi$ is a simple path from a leaf node in $T$ to another leaf node, and the sum of the radii of the balls along $\pi$ is the maximum among all such paths. Now, consider any path $\pi=\{\pi_{1},\dots,\pi_{m}\}$ between two leaves. Also, consider the graph $T^{\prime}=T-\pi$ , constructed by removing the vertices and edges of $\pi$ from $T$ . Note that $T^{\prime}$ is a collection of connected components each having exactly one ball $B^{\prime}_{i}$ connected to exactly one $\pi_{i}\in\pi$ with an edge of $T$ . We say that such a component is connected to $T$ via $\pi_{i}$ . A set of balls $Z\subseteq B$ is said to form a connected set if the subgraph of $G$ induced by the balls in $Z$ is connected.

Observation 13.

Consider a connected set $Z$ of balls with the sum of radii $\mathcal{R}^{\prime}$ . For any two points $a, b$ contained in the balls of $Z$ , $d(a,b)\leq 2\cdot\mathcal{R}^{\prime}$ .

Proof.

Let $B(c_{i},r_{i}),B(c_{j},r_{j})\in Z$ be the balls containing $a, b$ , respectively. Since $Z$ is a connected set, there is a simple path between $B(c_{i},r_{i})$ and $B(c_{j},r_{j})$ in $G$ that uses only balls of $Z$ . Thus, by triangle inequality, $d(c_{i},c_{j})\leq r_{i}+2(\mathcal{R}^{\prime}-r_{i}-r_{j})+r_{j}=2\cdot% \mathcal{R}^{\prime}-r_{i}-r_{j}$ . Hence, $d(a,b)\leq d(a,c_{i})+d(c_{i},c_{j})+d(c_{j},b)\leq 2\cdot\mathcal{R}^{\prime}$ . $\hfill\blacktriangleleft$

Similarly, we also have the following observation.

Observation 14.

Consider a connected set $Z$ of balls with the sum of radii $\mathcal{R}^{\prime}$ . For any point $p$ in a ball of $Z$ and a ball $B(c_{i},r_{i})\in Z$ , $d(c_{i},p)\leq 2\cdot\mathcal{R}^{\prime}-r_{i}$ .

Proof.

Let $B(c_{j},r_{j})\in Z$ be a ball containing $p$ . Since $Z$ is a connected set, there is a simple path between $B(c_{i},r_{i})$ and $B(c_{j},r_{j})$ in $G$ that uses only balls of $Z$ . Thus, by triangle inequality, $d(c_{i},p)\leq d(c_{i},c_{j})+d(c_{j},p)\leq r_{i}+2(\mathcal{R}^{\prime}-r_{i% }-r_{j})+r_{j}+d(c_{j},p)\leq 2\cdot\mathcal{R}^{\prime}-r_{i}$ . $\hfill\blacktriangleleft$

The proof of Lemma 11 is as follows.

Proof.

We prove the existence of the point $c$ with the desired property by considering Procedure 4 that explicitly computes a center. We clarify that this procedure is only for the purpose of analysis, and we do not run it as a part of our algorithm.

Algorithm 4 Find-Center

(B^{\prime})

.

Procedure 4 picks the new center according to two main cases: (i) there exists a ball in $B^{\prime}$ with radius at least $\frac{2}{3}\mathcal{R}$ , (ii) all balls in $B^{\prime}$ have radii less than $\frac{2}{3}\mathcal{R}$ .

In case (i), there exists a ball $B(c^{\prime}_{i},r^{\prime}_{i})$ such that $r^{\prime}_{i}\geq\frac{2}{3}\mathcal{R}$ . In this case, Procedure 4 picks $c^{\prime}_{i}$ as the new center. By Observation 14, we have that for any point $p\in P^{\prime}$ , $d(c^{\prime}_{i},p)\leq 2\cdot\mathcal{R}-r^{\prime}_{i}\leq 2\cdot\mathcal{R}% -\frac{2}{3}\mathcal{R}=\frac{4}{3}\mathcal{R}$ .

In case (ii), each ball in $B^{\prime}$ has a radius of less than $\frac{2}{3}\mathcal{R}$ . The center selection is split up into two subcases: (iia) $\text{Sum}_{L}\geq\frac{1}{3}\mathcal{R}$ , and (iib) $\text{Sum}_{L}<\frac{1}{3}\mathcal{R}$ .

We first consider case (iia), where a point $p$ contained in both $\pi_{i-1}$ and $\pi_{i}$ is chosen as the new center. As each ball has radius less than $\frac{2}{3}\mathcal{R}$ and $\pi_{1}$ is a leaf, while loop 7 cannot terminate with $i=1$ , i.e., at its termination $i\geq 2$ . Thus, $\pi_{i-1}$ is well-defined. Consider the partition of $B^{\prime}$ into two parts $B_{L}$ and $B_{R}$ . $B_{L}$ is the union of the balls $\pi_{1},\dots,\pi_{i-1}$ and any ball that lies in a component of $T-\pi$ that is connected to $T$ via $\pi_{j}$ for $1\leq j\leq i-1$ . Similarly, $B_{R}$ is the union of the balls $\pi_{i},\dots,\pi_{m}$ and any ball that lies in a component of $T-\pi$ that is connected to $T$ via $\pi_{j}$ for $i\leq j\leq m$ . Let $P_{L}=\{p_{L}\mid\text{point }p_{L}\text{ is in a ball of }B_{L}\}$ and $P_{R}=\{p_{R}\mid\text{point }p_{R}\text{ is in a ball of }B_{R}\}$ . Note that $P_{L}\cup P_{R}=P^{\prime}$ . Next, we bound the distance between the chosen center $p$ and the points in $P_{L}$ and $P_{R}$ . Note that by our definition of $p,P_{L},$ and $P_{R}$ , $p\in P_{L}\cap P_{R}$ . First, we consider $d(p,p_{L})$ for any $p_{L}\in P_{L}$ . Note that $\text{Sum}_{L}<\frac{2}{3}\mathcal{R}$ at the end of while loop 7. Also, by our definition of $\text{Sum}_{L}$ , it is the sum of the radii of the balls in $B_{L}$ . Then, as $B_{L}$ is a connected set of balls and $p\in P_{L}$ , by Observation 13, it follows that $d(p,p_{L})\leq 2\cdot\text{Sum}_{L}<\frac{4}{3}\mathcal{R}$ . Now we consider $d(p,p_{R})$ for any $p_{R}\in P_{R}$ . Since $\text{Sum}_{L}\geq\frac{1}{3}\mathcal{R}$ in this subcase and $(B_{L},B_{R})$ is a partition of $B^{\prime}$ , we know that the sum of the radii of the balls in $B_{R}$ , $\text{Sum}_{R}\leq\frac{2}{3}\mathcal{R}$ . Then, as $B_{R}$ is a connected set of balls and $p\in P_{R}$ , by Observation 13, it follows that $d(p,p_{R})\leq 2\cdot\text{Sum}_{R}\leq\frac{4}{3}\mathcal{R}$ . Thus, the lemma follows in this subcase.

Next, we consider case (iib), here, we pick center $c^{\prime}_{i}$ of ball $\pi_{i}=B(c^{\prime}_{i},r^{\prime}_{i})$ as the new center. Similar to case (iia), we partition $B^{\prime}$ into three parts $B_{L}$ , $B_{M}$ , and $B_{R}$ . $B_{L}$ is the union of the balls $\pi_{1},\dots,\pi_{i-1}$ and any ball that lies in a component of $T-\pi$ that is connected to $T$ via $\pi_{j}$ for $1\leq j\leq i-1$ . Similarly, $B_{M}$ is the union of the ball $\pi_{i}$ and any ball that lies in a component of $T-\pi$ that is connected to $T$ via $\pi_{i}$ . Lastly, $B_{R}$ is the union of the balls $\pi_{i+1},\dots,\pi_{m}$ and any ball that lies in a component of $T-\pi$ that is connected to $T$ via $\pi_{j}$ for $i+1\leq j\leq m$ . Let $P_{L}=\{p_{L}\mid\text{point }p_{L}\text{ is in a ball of }B_{L}\}$ , $P_{M}=\{p_{M}\mid\text{point }p_{M}\text{ is in a ball of }B_{M}\}$ , and $P_{R}=\{p_{R}\mid\text{point }p_{R}\text{ is in a ball of }B_{R}\}$ . Note that $P_{L}\cup P_{M}\cup P_{R}=P^{\prime}$ , so we can again bound the overall distance by considering $P_{L},P_{M},$ and $P_{R}$ separately. Towards this end, note that by the end of Loop 5, $\text{Sum}_{L}=\text{cost}(B_{L})$ and $\text{Sum}=\text{cost}(B_{L})+\text{cost}(B_{M})$ .

We first consider $d(p,p_{L})$ for any $p_{L}\in P_{L}$ . Note that $B_{L}\cup\{\pi_{i}\}$ is a connected set of balls with a sum of radii of $\text{Sum}_{L}+r^{\prime}_{i}$ . Furthermore, recall that $\text{Sum}_{L}<\frac{1}{3}\mathcal{R}$ by the assumption of case (iib), and $r^{\prime}_{i}<\frac{2}{3}\mathcal{R}$ by the assumption of case (ii). By Observation 14, we have that $d(c^{\prime}_{i},p_{L})\leq 2\cdot(\text{Sum}_{L}+r^{\prime}_{i})-r^{\prime}_{% i}=2\cdot\text{Sum}_{L}+r^{\prime}_{i}<2\cdot\frac{1}{3}\mathcal{R}+\frac{2}{3% }\mathcal{R}=\frac{4}{3}\mathcal{R}$ .

Next, we consider $d(p,p_{R})$ for some $p_{R}\in P_{R}$ . Note that $\text{cost}(B_{R})=\mathcal{R}-\text{Sum}$ . Since $\text{Sum}\geq\frac{2}{3}\mathcal{R}$ by the end of Loop 7, we have that $\text{cost}(B_{R})=\mathcal{R}-\text{Sum}\leq\frac{1}{3}\mathcal{R}$ . Note also that $B_{R}\cup\{\pi_{i}\}$ is a connected set of balls with a sum of radii of $\text{cost}(B_{R})+r^{\prime}_{i}$ . Since $r^{\prime}_{i}<\frac{2}{3}\mathcal{R}$ by the assumption of case (ii), by Observation 14 we have that for any $p_{R}\in P_{R}$ , $d(c_{i}^{\prime},p_{R})\leq 2\cdot(\text{cost}(B_{R})+r^{\prime}_{i})-r^{% \prime}_{i}=2\cdot\text{cost}(B_{R})+r^{\prime}_{i}<2\cdot\frac{1}{3}\mathcal{% R}+\frac{2}{3}\mathcal{R}=\frac{4}{3}\mathcal{R}$ .

Lastly, we consider $d(p,p_{M})$ for some $p_{M}\in P_{M}$ . Let $B_{l}\in B_{M}$ be a ball that contains $p_{M}$ . Consider any simple path $\pi^{\prime}$ in $T$ between any leaf ball in $B_{M}$ and $\pi_{i}$ such that $\pi^{\prime}$ also contains $B_{l}$ . Such a path exists, as $B_{l}$ lies in a component of $T-\pi$ that is connected to $T$ via $\pi_{i}$ . We denote by $\pi^{\prime}-\pi_{i}$ the path obtained by removing $\pi_{i}$ from $\pi^{\prime}$ . Note that

\text{Sum}_{L}+\text{cost}(\pi^{\prime}-\pi_{i})+r_{i}^{\prime}+\text{Sum}_{R}% \leq\mathcal{R}.

(1)

Since balls along the path $\pi$ have the maximum sum of radii, we have that

\text{cost}(\pi^{\prime}-\pi_{i})+r_{i}^{\prime}=\text{cost}(\pi^{\prime})\leq% \text{cost}(\pi)\leq\text{Sum}_{L}+r^{\prime}_{i}+\text{Sum}_{R}

and therefore

\text{cost}(\pi^{\prime}-\pi_{i})\leq\text{Sum}_{L}+\text{Sum}_{R}.

(2)

Combining Inequalities 1 and 2 we have that

2\cdot\text{cost}(\pi^{\prime}-\pi_{i})+r^{\prime}_{i}\leq\mathcal{R}.

(3)

Now, note that $\pi^{\prime}$ is a connected set of balls including $B_{l}\ni p_{M}$ with the sum of radii $\text{cost}(\pi^{\prime}-\pi_{i})+r^{\prime}_{i}$ . Thus, by Observation 14 we have that $d(c^{\prime}_{i},p_{M})\leq 2\cdot(\text{cost}(\pi^{\prime}-\pi_{i})+r^{\prime% }_{i})-r^{\prime}_{i}=2\cdot\text{cost}(\pi^{\prime}-\pi_{i})+r^{\prime}_{i}$ . Applying Inequality 3 we have that $d(c^{\prime}_{i},p_{M})\leq\mathcal{R}$ .

Since $d(p_{L},c^{\prime}_{i}),d(p_{M},c^{\prime}_{i}),d(p_{R},c^{\prime}_{i})\leq% \frac{4}{3}\mathcal{R}$ for all $p_{L}\in P_{L},p_{M}\in P_{M},$ and $p_{R}\in P_{R}$ , and $P_{L}\cup P_{M}\cup P_{R}$ covers all points in $P^{\prime}$ , $c^{\prime}_{i}$ is at a distance of at most $\frac{4}{3}\mathcal{R}$ from any point in $P^{\prime}$ in case (iib). This finishes the proof of the lemma. $\hfill\blacktriangleleft$

3.4 Guessing Radii

Here we describe a procedure for guessing the radii of any $k$ -MSR clustering up to $(1+\epsilon)$ factor. Formally, one can enumerate a set $R$ of $k$ -sized vectors such that for any $k$ -MSR clustering with radii $r_{1}\leq\ldots\leq r_{k}$ , there is a vector $(r_{1}^{\prime},\ldots,r_{k}^{\prime})$ in $R$ where for all $1\leq j\leq k$ , $r_{j}\leq r_{j}^{\prime}$ and if $r_{j}>\frac{\epsilon\cdot r_{k}}{k}$ , $r_{j}^{\prime}\leq(1+\epsilon)r_{j}$ . Moreover, the size of $R$ is only $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}$ . From now on, we call this type of enumeration process a guessing procedure, and we refer to each enumerated entry as a guess. Similar procedures have been used previously for guessing the radii of an optimal capacitated sum of radii clustering [24, 5, 19, 25, 13]. We restate those procedures to obtain a general algorithm that can enumerate the radii of all clusterings. In our algorithm, this procedure will be used to guess both a set of optimal vanilla radii and a set of optimal radii under any given mergeable constraint. Towards this end, we clarify that in the guessed radii vector $(r_{1}^{\prime},\ldots,r_{k}^{\prime})$ , all radii might not be distinct, and specifically we have $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ many distinct radii. So, we will enumerate $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ -sized vectors instead while keeping track of the multiplicities.

The procedure works in the following manner. Given a set of $n$ points $P$ in a metric space, and parameters $k$ and $\epsilon$ , we first compute a radius $r_{max}$ that can potentially be the maximum radius of some clustering; we can do this in $O(n^{2})$ time by trying distances between each pair of points in $P$ . For each $r_{max}$ , we set $[\frac{\epsilon\cdot r_{max}}{k},(1+\epsilon)r_{max}]$ as the range in which we guess the radii. The procedure is described as Algorithm 5.

Algorithm 5 Guess-Radii

(P,k,\epsilon)

.

Now we show some properties of the output size, runtime, and correctness of the procedure. First, we note the following observation about the number of distinct radii in each $R_{i}\in R$ .

Observation 15.

Each $R_{i}\in R$ from the output of Algorithm 5 has $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ distinct radii.

Proof.

Consider the radii vector $R_{i}=((1+\epsilon)^{m},\dots,(1+\epsilon)^{M})$ . Since $R_{i}$ is formed by picking powers of $1+\epsilon$ from the range $[\frac{\epsilon\cdot r_{max}}{k},(1+\epsilon)r_{max}]$ , the number of radii in $R_{i}$ is bounded by $M-m+1\leq 1+\log_{1+\epsilon}\frac{(1+\epsilon)\cdot r_{max}}{\frac{\epsilon% \cdot r_{max}}{k}}=O(\log_{1+\epsilon}\frac{k}{\epsilon})$ . $\hfill\blacktriangleleft$

Furthermore, we have the following observation about the size of $K$ , which will help us bound the runtime of both Algorithm 5 and some other algorithms.

Observation 16.

The size of $K$ is bounded by $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}$ .

Proof.

First, note that there are a total of $n^{2}$ choices for $r_{max}$ . Next, we consider the number of distinct radii vectors $K_{ij}=(k_{m},\dots,k_{M})$ that are computed for each $r_{max}$ . By Observation 15 we have that $M-m+1=|R_{i}|$ is bounded by $O(\log_{1+\epsilon}\frac{k}{\epsilon})$ . Since each $k_{t}\leq k$ , there are $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}$ possible vectors $K_{ij}$ for each choice of $r_{max}$ . It follows that there are a total of $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}$ many vectors in $K$ . $\hfill\blacktriangleleft$

Since Algorithm 5 enumerates each entry of $K$ , the next lemma follows.

Lemma 17.

Algorithm 5 runs in $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}$ time.

Next, we show that for any clustering, Algorithm 5 outputs a solution with a correct guess.

Lemma 18.

For any $k$ -MSR clustering with radii $r_{1},\ldots,r_{k}$ , there are vectors $R_{i}=(r_{1}^{\prime},\ldots,r_{l}^{\prime})$ in $R$ and $K_{ij}=(k_{1}^{\prime},\ldots,k_{l}^{\prime})$ in $K$ for some $i, j$ such that there exist exactly $k_{t}^{\prime}$ indices $\kappa\in\{1,\dots,k\}$ with $r_{\kappa}\leq r_{t}^{\prime}<(1+\epsilon)r_{\kappa}$ for $2\leq t\leq l$ and $k_{1}^{\prime}$ indices $\kappa\in\{1,\dots,k\}$ with $r_{\kappa}\leq r_{1}^{\prime}$ . Moreover, $\sum_{t=1}^{l}k_{t}^{\prime}\cdot r_{t}^{\prime}\leq(1+\epsilon)\sum_{i=1}^{k}% r_{i}$ .

Proof.

Consider the choice of $r_{max}$ made in Algorithm 5 so that $r_{max}=\max_{i=1}^{k}r_{i}$ . Also consider the vector $R_{i}=(r_{1}^{\prime},\ldots,r_{l}^{\prime})$ in $R$ corresponding to this choice. By definition, $r_{l}^{\prime}\leq(1+\epsilon)r_{max}$ and $r_{1}^{\prime}\geq\frac{\epsilon\cdot r_{max}}{k}$ . Define $k_{1}^{\prime}$ to be the number of radii in $\{r_{1},\ldots,r_{k}\}$ that are at most $r_{1}^{\prime}$ . For $2\leq t\leq l$ , define $k_{t}^{\prime}$ to be the number of radii in $\{r_{1},\ldots,r_{k}\}$ that are also in $(r_{t-1}^{\prime},r_{t}^{\prime}]$ . By definition, $\sum_{t=1}^{l}k_{t}^{\prime}=k$ , and so $(k_{1}^{\prime},\ldots,k_{l}^{\prime})$ is a vector in $K$ which is considered w.r.t $r_{max}$ . Also by definition of $k_{t}^{\prime}$ for $2\leq t\leq l$ , there are $k_{t}^{\prime}$ indices $\kappa\in\{1,\dots,k\}$ with $r_{\kappa}\in(r_{t-1}^{\prime},r_{t}^{\prime}]$ , i.e., $r_{\kappa}\leq r_{t}^{\prime}<(1+\epsilon)r_{\kappa}$ as desired.

Next, we prove the moreover part. The sum of the $k_{1}^{\prime}$ radii $r_{1}^{\prime}$ is at most $k_{1}^{\prime}(1+\epsilon)\frac{\epsilon\cdot r_{max}}{k}\leq 2\epsilon\cdot r% _{max}\leq 2\epsilon\sum_{i=1}^{k}r_{i}$ . Also, for $2\leq t\leq l$ , $k_{t}^{\prime}\cdot r_{t}^{\prime}\leq\sum_{\kappa\in\{1,\dots,k\}\mid r_{% \kappa}\in(r_{t-1}^{\prime},r_{t}^{\prime}]}(1+\epsilon)r_{\kappa}$ . Summing over all $2\leq t\leq l$ , $\sum_{t=2}^{l}k_{t}^{\prime}\cdot r_{t}^{\prime}\leq(1+\epsilon)\sum_{i=1}^{k}% r_{i}$ . Hence, $\sum_{t=1}^{l}k_{t}^{\prime}\cdot r_{t}^{\prime}\leq(1+3\epsilon)\sum_{i=1}^{k% }r_{i}$ . Scaling $\epsilon$ down by a factor of 3, we obtain the lemma. $\hfill\blacktriangleleft$

Corollary 19.

For any optimal sum of radii clustering (vanilla or constrained) $\mathcal{C}$ , there are vectors $R_{i}=(r_{1}^{\prime},\ldots,r_{l}^{\prime})$ in $R$ and $K_{ij}=(k_{1}^{\prime},\ldots,k_{l}^{\prime})$ in $K$ for some $i, j$ such that there is a feasible $(1+\epsilon)$ -approximate clustering that uses $k_{t}^{\prime}$ balls of radius $r_{t}^{\prime}$ for all $1\leq t\leq l$ .

Proof.

Let ${r}_{1},\ldots,{r}_{k}$ be the radii of an optimal clustering. Fix the vectors $R_{i}=(r_{1}^{\prime},\ldots,r_{l}^{\prime})$ and $K_{ij}=(k_{1}^{\prime},\ldots,k_{l}^{\prime})$ given by Lemma 18. We show that each cluster of $\mathcal{C}$ can be covered by a ball of radius $r_{\tau}^{\prime}$ for some $\tau$ such that $k_{t}^{\prime}$ balls of radius $r_{t}^{\prime}$ are used for all $1\leq t\leq l$ . As the clustering induced by these balls is essentially the same clustering $\mathcal{C}$ , it remains feasible. To cover each cluster of $\mathcal{C}$ that uses a ball of radius $r_{\kappa}$ , if $r_{\kappa}\leq r_{1}^{\prime}$ , use the same center, but with radius $r_{1}^{\prime}$ ; otherwise, as $\sum_{t=1}^{l}k_{t}^{\prime}=k$ , there is $2\leq\tau\leq l$ with $r_{\kappa}\leq r_{\tau}^{\prime}<(1+\epsilon)r_{\kappa}$ , and in this case use the same center, but with radius $r_{\tau}^{\prime}$ . By the correspondence of the radii $\{r_{\kappa}\}$ and $\{r_{t}^{\prime}\}$ in Lemma 18, $k_{t}^{\prime}$ balls of radius $r_{t}^{\prime}$ are used for all $1\leq t\leq l$ . Lastly, as $\sum_{t=1}^{l}k_{t}^{\prime}\cdot r_{t}^{\prime}\leq(1+\epsilon)\sum_{i=1}^{k}% r_{i}$ , the new set of balls induces a $(1+\epsilon)$ -approximate clustering. $\hfill\blacktriangleleft$

3.5 The Algorithm and its Analysis

With all of the procedures defined, we state the main algorithm. Let $k>0$ and $\epsilon>0$ be some constants, our algorithm is given as Algorithm 6.

Algorithm 6 Mergeable-Constraint-

k

-MSR

(P,k,\epsilon)

.

We now analyze Algorithm 6, starting with the correctness and approximation factor. We have the following Lemma.

Lemma 20.

Algorithm 6 produces a $(4+\epsilon)$ -approximate $k$ -MSR clustering satisfying a given mergeable constraint.

Proof.

Let $OPT_{v}$ and $OPT_{c}$ be the respective optimal cost of vanilla $k$ -MSR and $k$ -MSR with the given mergeable constraint. By Corollary 19, there are vectors $R_{i}=(r_{1}^{\prime},\ldots,r_{l}^{\prime})$ in $R$ and $K_{ii^{\prime}}=(k_{1}^{\prime},\ldots,k_{l}^{\prime})$ in $K$ for some $i,i^{\prime}$ such that there is a feasible $(1+\epsilon)$ -approximate vanilla clustering that uses $k_{t}^{\prime}$ balls of radius $r_{t}^{\prime}$ for all $1\leq t\leq l$ . Fix this choice of $R_{i}$ and $K_{ii^{\prime}}$ in Line 2. Then by Lemma 4, $\text{Vanilla-Clustering}(P,R_{i},K_{ii^{\prime}})$ (Algorithm 1) outputs a feasible $(2+2\epsilon)$ vanilla clustering $(C_{v},\phi_{v})$ . Let $c_{1},\dots,c_{k}$ be the centers in $C_{v}$ . Similarly, by Corollary 19, there are vectors $R_{j}=(r_{1},\ldots,r_{l})$ in $R$ and $K_{jj^{\prime}}=(k_{1},\ldots,k_{l})$ in $K$ for some $j,j^{\prime}$ such that there is a feasible $(1+\epsilon)$ -approximate clustering $\mathcal{C}^{*}$ with the given mergeable constraint that uses $k_{t}$ balls of radius $r_{t}$ for all $1\leq t\leq l$ . Fix this choice of $R_{j}$ and $K_{jj^{\prime}}$ in Line 7. Then by Lemma 6, the output $R_{e}^{jj^{\prime}}$ of $\text{Expand-Balls}(C_{v},\phi_{v},R_{j},K_{jj^{\prime}})$ (Algorithm 2) and hence $R_{e}$ contains a vector $(r_{1}^{c},\dots,r_{k}^{c})$ such that each cluster of $\mathcal{C}^{*}$ is contained in $B(c_{j},r_{j}^{c})$ for some $1\leq j\leq k$ . Moreover, by the same lemma, $\sum_{\mu=1}^{k}r_{\mu}^{c}\leq\sum_{\tau=1}^{k}r_{\tau}^{\prime}+\sum_{t=1}^{% l}k_{t}\cdot r_{t}\leq(2+2\epsilon)OPT_{v}+(1+\epsilon)OPT_{c}\leq(3+3\epsilon% )OPT_{c}$ . This is true, as the optimal vanilla clustering cost is at most the optimal cost of any constrained clustering.

Fix the above choice of $(r_{1}^{c},\dots,r_{k}^{c})\in R_{e}$ in Line 10. Then $B=\{B(c_{1},r_{1}^{c}),\dots,B(c_{l},r_{k}^{c})\}$ , and hence by Lemma 9, the clustering $(C_{j},\phi_{j})$ returned by $\text{Merge-Balls}(B)$ (Algorithm 3) satisfies the mergeable constraint. Moreover, by Corollary 12, the cost of $(C_{j},\phi_{j})$ is at most $\frac{4}{3}\sum_{\mu=1}^{k}r_{\mu}^{c}\leq\frac{4}{3}(3+3\epsilon)OPT_{c}=(4+4% \epsilon)OPT_{c}$ . Scaling $\epsilon$ by a constant, we obtain the lemma. $\hfill\blacktriangleleft$

Now we analyze the runtime of Algorithm 6. We have the following lemma.

Lemma 21.

Algorithm 6 runs in $2^{O(\frac{k}{\epsilon}\cdot\log^{2}\frac{k}{\epsilon})}n^{4}$ time.

Proof.

We first show the runtime of each part of the algorithm. By Lemma 17 we have that the Guess-Radii procedure has a runtime of $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}$ . Next, by Observation 16 we also have that Guess-Radii produces $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}$ many vectors in $K$ . By Lemma 5 we have that the Vanilla-Clustering procedure runs in $O((\log_{1+\epsilon}\frac{k}{\epsilon})^{k}\cdot n)$ time; since we run Vanilla-Clustering on each pair $R_{i}\in R$ and $K_{ii^{\prime}}\in K$ , this step of the algorithm has a runtime of

		$\displaystyle k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}\cdot(\log_{1+% \epsilon}\frac{k}{\epsilon})^{k}\cdot n$
	$\displaystyle=\$	$\displaystyle k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}\cdot(\log_{1+% \epsilon}\frac{k}{\epsilon})^{k}n^{3}.$

Moving on to the expand radii step, by Lemma 8 we have that the Expand-Balls procedure runs in $(O(\log_{1+\epsilon}\frac{k}{\epsilon}))^{k}$ time. Also, Expand-Balls runs for each of the $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}$ pairs $R_{j}\in R$ and $K_{jj^{\prime}}\in K$ , resulting in a runtime of $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}\cdot(\log_{1+\epsilon}\frac{k}{% \epsilon})^{k}n^{2}$ . The next step of the algorithm, Merge-Balls, runs in $O(kn^{2})$ time by Lemma 10. We also showed in Lemma 7 that Expand-Balls outputs $(O(\log_{1+\epsilon}\frac{k}{\epsilon}))^{k}$ pairs $R_{j}\in R$ and $K_{jj^{\prime}}\in K$ , so the total number of guesses for expanded radii is bounded by $k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}\cdot(\log_{1+\epsilon}\frac{k}{% \epsilon})^{k}n^{2}$ . Since Algorithm 6 runs Merge-Balls for each set of guessed radii $R^{\prime}_{j}\in R_{e}$ , this step has a runtime of

		$\displaystyle k\cdot n^{2}\cdot k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}% \cdot(\log_{1+\epsilon}\frac{k}{\epsilon})^{k}n^{2}$
	$\displaystyle=\$	$\displaystyle k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}\cdot(\log_{1+% \epsilon}\frac{k}{\epsilon})^{k}n^{4}.$

Adding everything together we have that Algorithm 6 runs in time

		$\displaystyle k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}n^{2}+k^{O({\log_{1+% \epsilon}}\frac{k}{\epsilon})}\cdot(\log_{1+\epsilon}\frac{k}{\epsilon})^{k}n^% {3}+$
		$\displaystyle k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}\cdot(\log_{1+% \epsilon}\frac{k}{\epsilon})^{k}n^{2}+k^{O({\log_{1+\epsilon}}\frac{k}{% \epsilon})}\cdot(\log_{1+\epsilon}\frac{k}{\epsilon})^{k}n^{4}$
	$\displaystyle=\$	$\displaystyle k^{O({\log_{1+\epsilon}}\frac{k}{\epsilon})}\cdot(\log_{1+% \epsilon}\frac{k}{\epsilon})^{k}n^{4}$
	$\displaystyle=\$	$\displaystyle 2^{O(\frac{k}{\epsilon}\cdot\log^{2}\frac{k}{\epsilon})}n^{4}.\$

$\hfill\blacktriangleleft$

Lemma 20 and Lemma 21 together produces Theorem 1.

Theorem 1. [Restated, see original statement.]

For any $\epsilon>0$ , there is a $(4+\epsilon)$ -approximation algorithm for the $k$ -MSR problem under mergeable constraints that runs in $2^{O(\frac{k}{\epsilon}\cdot\log^{2}\frac{k}{\epsilon})}n^{4}$ time.

4 Hardness of Clustering with Mergeable Constraints

Definition 22 (Fair Representational Clustering).

We are given $\ell$ disjoint groups of points, denoted as $P_{1},\ldots,P_{\ell}$ , with a total of $n$ points with a distance metric $d$ . Each group $P_{i}$ is associated with fairness parameters $\alpha_{i},\beta_{i}\in[0,1]$ , for $1\leq i\leq\ell$ . A clustering is said to be fair representational if, within every cluster, the proportion of points from group $i$ lies between $\alpha_{i}$ and $\beta_{i}$ , for all $i$ . The objective is to find a fair representational clustering with $k$ clusters, that minimizes the sum of the radii of the clusters.

As shown by Carta et al. [11], the fair representational constraint is mergeable. We prove that Fair Representational Clustering cannot be solved in time $f(k)n^{o(k)}$ unless ETH is false. Specifically, we show a reduction from the Dominating set problem.

Given an instance of Dominating set containing an $n$ -vertex graph $G=(V,E)$ and a parameter $k$ , we construct a new graph $G^{\prime}$ . Initially, $G^{\prime}=G$ . Add two sets $V_{1},V_{2}$ of $k$ vertices each to $G^{\prime}$ and the edges $\{v,v_{i}\},\{v,v_{j}\}$ for all $v\in V,v_{i}\in V_{1},v_{j}\in V_{2}$ . The instance $\mathcal{I}$ of Fair Representational Clustering is defined as follows: $\ell=3$ , $P_{1}=V$ , $P_{2}=V_{1}$ , $P_{3}=V_{2}$ , $d$ is the shortest path metric in $G^{\prime}$ , $\alpha_{1}=1/3,\beta_{1}=1$ , and for $i\in\{2,3\}$ , $\alpha_{i}=1/(n+2)$ and $\beta_{i}=1$ .

Lemma 23.

Dominating set admits a solution of size $k$ if and only if there is a fair representational clustering of $\cup_{i=1}^{3}P_{i}$ with $k$ clusters of cost $k$ .

Proof.

The forward direction is easy to prove. Suppose Dominating set admits a solution $V^{\prime}=\{v_{1},v_{2},\ldots,v_{k}\}$ . We construct a clustering $(C,\phi)$ of $\cup_{i=1}^{3}P_{i}$ as follows. Use the points $\{v_{1},v_{2},\ldots,v_{k}\}$ in $P_{1}$ as centers. For each $v\in P_{1}$ , assign $v$ to a center $v_{j}$ that dominates $v$ . Assign the $j$ -th points of $P_{2}$ and $P_{3}$ to $v_{j}$ . It is easy to verify that each cluster has radius 1, so the total cost is $k$ . Also in each cluster, the proportion of points of $P_{1}$ is at least $1/3$ , the proportion of points of $P_{2}$ is at least $1/(n+2)$ , and the same for $P_{3}$ . So, $(C,\phi)$ is a fair representational clustering.

Now, suppose there is a fair representational clustering of $\cup_{i=1}^{3}P_{i}$ with $k$ clusters of cost $k$ . First, we argue that each cluster has a non-zero radius, as otherwise, it is a singleton cluster, which is not fair. This implies that the radius of each cluster is 1. Now, each cluster center must be in $P_{1}=V$ , as the distance between any two points $u\in P_{2},u^{\prime}\in P_{3}$ is 2, excluding them to be a center of a fair cluster of radius 1. It follows that any point $v\in P_{1}$ is at a distance at most $1$ from the $k$ cluster centers. Hence, these vertices in $V$ form a dominating set of size $k$ . $\hfill\blacktriangleleft$

Since it is not possible to solve Dominating set in $f(k)n^{o(k)}$ time unless ETH is false [17], we obtain Theorem 2.

Theorem 2. [Restated, see original statement.]

Fair Representational Clustering cannot be solved in time $f(k)n^{o(k)}$ unless ETH is false.

References

[1] Sara Ahmadian and Chaitanya Swamy. Approximation algorithms for clustering problems with lower bounds and outliers. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP, volume 55 of LIPIcs, pages 69:1–69:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ICALP.2016.69.
[2] Sara Ahmadian and Chaitanya Swamy. Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2016.69.
[3] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544–562, 2004. doi:10.1137/S0097539702416402.
[4] Sayan Bandyapadhyay, Eden Chlamtáč, Yury Makarychev, and Ali Vakilian. A polynomial-time approximation for pairwise fair $k$ -median clustering. arXiv preprint arXiv:2405.10378, 2024. doi:10.48550/arXiv.2405.10378.
[5] Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 12:1–12:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.SOCG.2023.12.
[6] Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav. Improved fixed-parameter bounds for min-sum-radii and diameters k-clustering and their fair variants. Proceedings of the AAAI Conference on Artificial Intelligence, 39(15):15481–15488, April 2025. doi:10.1609/aaai.v39i15.33699.
[7] Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Advances in Neural Information Processing Systems, pages 4954–4965, 2019.
[8] Ioana O Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.18.
[9] Moritz Buchem, Katja Ettmayr, Hugo KK Rosado, and Andreas Wiese. A (3)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1738–1765. SIAM, 2024.
[10] Lena Carta, Lukas Drexler, Annika Hennes, Clemens Rösner, and Melanie Schmidt. FPT Approximations for Fair k-Min-Sum-Radii. In Julián Mestre and Anthony Wirth, editors, 35th International Symposium on Algorithms and Computation (ISAAC 2024), volume 322 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:18, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ISAAC.2024.16.
[11] Lena Carta, Lukas Drexler, Annika Hennes, Clemens Rösner, and Melanie Schmidt. Fpt approximations for fair $k$ -min-sum-radii, 2024. doi:10.48550/arXiv.2410.00598.
[12] Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci., 68(2):417–441, 2004. doi:10.1016/j.jcss.2003.07.014.
[13] Xianrun Chen, Dachuan Xu, Yicheng Xu, and Yong Zhang. Parameterized approximation algorithms for sum of radii clustering and variants. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20666–20673, 2024. doi:10.1609/AAAI.V38I18.30053.
[14] Anshuman Chhabra, Karina Masalkovaitė, and Prasant Mohapatra. An overview of fairness in clustering. IEEE Access, 2021. doi:10.1109/ACCESS.2021.3114099.
[15] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems, pages 5029–5037, 2017. URL: https://proceedings.neurips.cc/paper/2017/hash/978fce5bcc4eccc88ad48ce3914124a2-Abstract.html.
[16] Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm for k-median, 2021. arXiv:2111.04589.
[17] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[18] Lukas Drexler, Annika Hennes, Abhiruk Lahiri, Melanie Schmidt, and Julian Wargalla. Approximating fair k-min-sum-radii in euclidean space. In International Workshop on Approximation and Online Algorithms, pages 119–133. Springer, 2023. doi:10.1007/978-3-031-49815-2_9.
[19] Arnold Filtser and Ameet Gadekar. Fpt approximations for capacitated sum of radii and diameters. arXiv preprint arXiv:2409.04984, 2024. doi:10.48550/arXiv.2409.04984.
[20] Zachary Friggstad and Mahya Jamshidian. Improved polynomial-time approximations for clustering with minimum sum of radii or diameters. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 56:1–56:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.56.
[21] Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On clustering to minimize the sum of radii. SIAM J. Comput., 41(1):47–60, 2012. doi:10.1137/100798144.
[22] Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985. doi:10.1016/0304-3975(85)90224-5.
[23] Dorit S Hochbaum and David B Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 10(2):180–184, 1985. doi:10.1287/MOOR.10.2.180.
[24] Tanmay Inamdar and Kasturi Varadarajan. Capacitated Sum-Of-Radii Clustering: An FPT Approximation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 62:1–62:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2020.62.
[25] Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. FPT approximation for capacitated sum of radii. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 of LIPIcs, pages 65:1–65:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ITCS.2024.65.

[bib.bib1] [1] Sara Ahmadian and Chaitanya Swamy. Approximation algorithms for clustering problems with lower bounds and outliers. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP, volume 55 of LIPIcs, pages 69:1–69:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ICALP.2016.69.

[bib.bib2] [2] Sara Ahmadian and Chaitanya Swamy. Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2016.69.

[bib.bib3] [3] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544–562, 2004. doi:10.1137/S0097539702416402.

[bib.bib4] [4] Sayan Bandyapadhyay, Eden Chlamtáč, Yury Makarychev, and Ali Vakilian. A polynomial-time approximation for pairwise fair $k$ -median clustering. arXiv preprint arXiv:2405.10378, 2024. doi:10.48550/arXiv.2405.10378.

[bib.bib5] [5] Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 12:1–12:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.SOCG.2023.12.

[bib.bib6] [6] Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav. Improved fixed-parameter bounds for min-sum-radii and diameters k-clustering and their fair variants. Proceedings of the AAAI Conference on Artificial Intelligence, 39(15):15481–15488, April 2025. doi:10.1609/aaai.v39i15.33699.

[bib.bib7] [7] Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Advances in Neural Information Processing Systems, pages 4954–4965, 2019.

[bib.bib8] [8] Ioana O Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.18.

[bib.bib9] [9] Moritz Buchem, Katja Ettmayr, Hugo KK Rosado, and Andreas Wiese. A (3)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1738–1765. SIAM, 2024.

[bib.bib10] [10] Lena Carta, Lukas Drexler, Annika Hennes, Clemens Rösner, and Melanie Schmidt. FPT Approximations for Fair k-Min-Sum-Radii. In Julián Mestre and Anthony Wirth, editors, 35th International Symposium on Algorithms and Computation (ISAAC 2024), volume 322 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:18, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ISAAC.2024.16.

[bib.bib11] [11] Lena Carta, Lukas Drexler, Annika Hennes, Clemens Rösner, and Melanie Schmidt. Fpt approximations for fair $k$ -min-sum-radii, 2024. doi:10.48550/arXiv.2410.00598.

[bib.bib12] [12] Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci., 68(2):417–441, 2004. doi:10.1016/j.jcss.2003.07.014.

[bib.bib13] [13] Xianrun Chen, Dachuan Xu, Yicheng Xu, and Yong Zhang. Parameterized approximation algorithms for sum of radii clustering and variants. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20666–20673, 2024. doi:10.1609/AAAI.V38I18.30053.

[bib.bib14] [14] Anshuman Chhabra, Karina Masalkovaitė, and Prasant Mohapatra. An overview of fairness in clustering. IEEE Access, 2021. doi:10.1109/ACCESS.2021.3114099.

[bib.bib15] [15] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems, pages 5029–5037, 2017. URL: https://proceedings.neurips.cc/paper/2017/hash/978fce5bcc4eccc88ad48ce3914124a2-Abstract.html.

[bib.bib16] [16] Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm for k-median, 2021. arXiv:2111.04589.

[bib.bib17] [17] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib18] [18] Lukas Drexler, Annika Hennes, Abhiruk Lahiri, Melanie Schmidt, and Julian Wargalla. Approximating fair k-min-sum-radii in euclidean space. In International Workshop on Approximation and Online Algorithms, pages 119–133. Springer, 2023. doi:10.1007/978-3-031-49815-2_9.

[bib.bib19] [19] Arnold Filtser and Ameet Gadekar. Fpt approximations for capacitated sum of radii and diameters. arXiv preprint arXiv:2409.04984, 2024. doi:10.48550/arXiv.2409.04984.

[bib.bib20] [20] Zachary Friggstad and Mahya Jamshidian. Improved polynomial-time approximations for clustering with minimum sum of radii or diameters. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 56:1–56:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.56.

[bib.bib21] [21] Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On clustering to minimize the sum of radii. SIAM J. Comput., 41(1):47–60, 2012. doi:10.1137/100798144.

[bib.bib22] [22] Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985. doi:10.1016/0304-3975(85)90224-5.

[bib.bib23] [23] Dorit S Hochbaum and David B Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 10(2):180–184, 1985. doi:10.1287/MOOR.10.2.180.

[bib.bib24] [24] Tanmay Inamdar and Kasturi Varadarajan. Capacitated Sum-Of-Radii Clustering: An FPT Approximation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 62:1–62:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2020.62.

[bib.bib25] [25] Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. FPT approximation for capacitated sum of radii. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 of LIPIcs, pages 65:1–65:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ITCS.2024.65.

Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Contributions

Theorem 1.

Theorem 2.

1.2 Related Work

Roadmap.

2 Preliminaries

3 An FPT (𝟒+ϵ)-approximation Algorithm

3.1 Finding a Vanilla Clustering

Observation 3.

Proof.

Lemma 4.

Proof.

Lemma 5.

Proof.

3.2 Expanding the Vanilla Clustering

Lemma 6.

Proof.

Lemma 7.

Proof.

Lemma 8.

3.3 Merging Balls

Lemma 9.

Proof.

Lemma 10.

Proof.

Lemma 11.

Corollary 12.

Observation 13.

Proof.

Observation 14.

Proof.

Proof.

3.4 Guessing Radii

Observation 15.

Proof.

Observation 16.

Proof.

Lemma 17.

Lemma 18.

Proof.

Corollary 19.

Proof.

3.5 The Algorithm and its Analysis

Lemma 20.

Proof.

Lemma 21.

Proof.

Theorem 1. [Restated, see original statement.]

4 Hardness of Clustering with Mergeable Constraints

Definition 22 (Fair Representational Clustering).

Lemma 23.

Proof.

Theorem 2. [Restated, see original statement.]

References

3 An FPT $(4+\epsilon)$ -approximation Algorithm