FPT Approximations for Capacitated Sum of Radii and Diameters

Filtser, Arnold; Gadekar, Ameet

doi:10.4230/LIPIcs.SoCG.2026.48

FPT Approximations for Capacitated Sum of Radii and Diameters

Arnold Filtser

Bar-Ilan University, Ramat Gan, Israel Ameet Gadekar

CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Abstract

The Capacitated Sum of Radii problem involves partitioning a set of points $P$ , where each point $p\in P$ has capacity $U_{p}$ , into $k$ clusters that minimize the sum of cluster radii, such that the number of points in the cluster centered at point $p$ is at most $U_{p}$ . We begin by showing that the problem is APX-hard, and that under gap-ETH there is no parameterized approximation scheme (FPT-AS). We then construct a $\approx 5.83$ -approximation algorithm in FPT time (improving a previous $\approx 7.61$ approximation in FPT time). Our results also hold when the objective is a general monotone symmetric norm of radii. We also improve the approximation factors for the uniform capacity case, and for the closely related problem of Capacitated Sum of Diameters.

Keywords and phrases:

clustering, sum of radii, sum of diameter, capacitated clustering, fpt

Funding:

Arnold Filtser: This research was supported by the Israel Science Foundation (Grant No. 1042/22).

Ameet Gadekar: This work was partially supported by the Israel Science Foundation (Grant No. 1042/22) while the author was affiliated with Bar-Ilan University.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms ; Theory of computation

\rightarrow

Approximation algorithms analysis ; Theory of computation

\rightarrow

Fixed parameter tractability ; Theory of computation

\rightarrow

Facility location and clustering

Related Version:

The reader is encouraged to read the full version of the paper: https://arxiv.org/pdf/2409.04984

Acknowledgements:

The authors thank the anonymous reviewer for suggesting the construction used in Theorem 2, which improves upon the one presented in an earlier version of the paper.

DOI:

10.4230/LIPIcs.SoCG.2026.48

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

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

1 Introduction

Clustering is a fundamental problem in several domains of computer science, including, data mining, operation research, and computational geometry, among others. In particular, center based clustering problems such as $k$ -median, $k$ -means, and $k$ -center have received significant attention from the research community for more than half a century [66, 55, 69, 9, 7, 61, 38, 53, 68, 59, 23, 15, 33, 32, 31, 34, 25, 1, 49]. In these problems, we are given a set $P$ of $n$ points together with a distance function (metric) and a positive integer $k$ . The goal is to partition $P$ into $k$ parts called clusters and choose a center point for each cluster, so that to minimize a clustering objective that is a function of the point distances to their centers. A related fundamental problem that helps reduce dissection effect due to $k$ -center [70, 28] (see Figure 1) is called Sum of Radii. Here the goal is to choose $k$ -size subset $X$ of $P$ (called centers, as before) and assign every point to an element in $X$ . This partitions the set $P$ into possible $k$ clusters, $C_{1},\cdots,C_{k}$ , where cluster $C_{i}$ corresponds to the set of points assigned to $x_{i}\in X$ . The radius of cluster $C_{i}$ centered at $x_{i}\in X$ is the maximum distance of a point in $P_{i}$ to $x_{i}$ . The objective is the sum of radii of the clusters $C_{1},\cdots,C_{k}$ .¹¹1Alternatively, in the Sum of Radii problem we choose centers $x_{1},\dots,x_{k}\in X$ , and radii $r_{1},\dots,r_{k}\in\mathbb{R}_{\geq 0}$ so that $P\subseteq\cup_{i=1}^{k}{\sf ball}(x_{i},r_{i})$ . The objective is to minimize $\sum_{i=1}^{k}r_{i}$ .

In the recent years Sum of Radii received a great share of interest in all aspects [28, 45, 46, 46, 14, 43, 21, 29, 56, 11, 58, 12, 3, 17, 42, 18]. Nevertheless, its computational landscape is not yet fully understood. While, the problem is NP-hard [45] even in weighted planar graphs and in metrics of bounded doubling dimensions, it is known to admit a QPTAS (quasi polynomial time approximation scheme) [45] in general metrics, thus prompting a possibility of PTAS (polynomial time approximation scheme).²²2If Sum of Radii is APX-hard (equivalently, does not admit a PTAS) then NP $\subseteq$ QP (in particular there is a quasi-polynomial time algorithm solving SAT). It is widely believed that NP $\not\subseteq$ QP. This is in contrast to related clustering problems like $k$ -center, $k$ -median, and $k$ -means which are all known to be APX-hard [55, 57, 8]. Currently, the present best known approximation factor in polynomial time is $(3+\varepsilon)$ due to Buchem, Ettmayr, Rosado, and Wiese [21] (improving over previous results of [28, 43]). Additionally, there is a recent $(2+\varepsilon)$ -approximation algorithm [29] that runs in FPT time³³3In this paper, by FPT time, we mean FPT w.r.t. the parameter $k$ . (fixed parameter tractable).

Figure 1: The optimal

3

-center solution (middle) splits the ground-truth clusters, whereas the Sum of Radii objective (right) avoids this dissection.

Capacitated clustering

We are interested in a much more challenging generalization where each point $p$ has an inherent capacity $U_{p}\geq 0$ , indicating an upper bound on the number of points it can serve as a center of a cluster in the solution.⁴⁴4Formally, following Footnote 1, a valid solution to the capacitated version also contains an assignment $\sigma:P\rightarrow\{x_{1},\dots,x_{k}\}$ such that if $\sigma(p)=x_{i}$ then $\delta(p,x_{i})\leq r_{i}$ , and for every $i$ , $|\sigma^{-1}(x_{i})|\leq U_{x_{i}}$ . This is known as the Non-Uniform Capacitated clustering problem. If all the points have the same capacity $U$ , the problem is referred to as the Uniform Capacitated clustering problem. Capacitated clustering naturally models many applications: in load balancing, cluster centers correspond to servers with limited service capacity, the radius captures latency, and minimizing the sum of radii models reducing aggregate latency subject to serve load; in wireless sensors, each cluster head can accommodate only bounded number of devices due to bandwidth, memory, or battery limitations, the radius corresponds to communication range, and optimizing the sum of radii reflects minimizing total communication energy. Capacitated clustering is thoroughly studied: Capacitated $k$ -center admits a constant factor approximation in polynomial time for both uniform [60] and non-uniform capacities [37, 5]. There are several bi-criteria polytime approximations for $k$ -median [30, 22, 24, 39, 63, 64].

There are FPT approximation algorithms for capacitated $k$ -median and capacitated $k$ -means with approximation factors $(3+\varepsilon)$ and $(9+\varepsilon)$ respectively [35] (improving over [2, 73]). On the other hand, assuming gap-ETH⁵⁵5Informally, gap-ETH says that there exists an $\varepsilon>0$ such that no sub-exponential time algorithm for $3$ -SAT can distinguish whether a given $3$ -SAT formula has a satisfying assignment or every assignment satisfies at most $(1-\varepsilon)$ fraction of the clauses., in FPT time it is impossible to approximate $k$ -median and $k$ -means with factors better than $(1+\frac{2}{e})$ and $(1+\frac{8}{e})$ , respectively (even without capacities) [32]. There is a $4+\varepsilon$ FPT-approximation for uniform capacitated $k$ -center [58, 50]⁶⁶6In fact, [50] obtained a $2$ -approximation for capacitated $k$ -center under soft assignments (where different centers can be co-located). In contrast, in this paper we consider only hard assignments (where we can open only a single center at each point). One can use [50] to obtain a $4$ -approximation for uniform capacitated $k$ -center w.r.t. hard assignments. See Section 3 for a further discussion..

For capacitated Sum of Radii (CapSoR) (see Table 1 for a summary of previous and new results), Inamdar and Varadarajan [56] constructed an FPT time algorithm providing an $28$ -approximation for Sum of Radii with uniform capacities. This was later improved to $4+\varepsilon$ by Bandyapadhyay, Lochet, and Saurabh [11], and finally to $3+\varepsilon$ by Jaiswal, Kumar, and Yadav [58]. For non-uniform capacities, the latter paper obtained $(4+\sqrt{13}+\varepsilon)\approx 7.61$ approximation in FPT time, improving over the previous approximation of $15+\varepsilon$ [11].

From the lower bound side, the authors in [58] showed that assuming ETH⁷⁷7Informally, ETH (Exponential Time Hypothesis), says that there is no subexponential time algorithm for $3$ -SAT., there is some constant $\beta>0$ , such that any $\beta$ -approximation for CapSoR (with non-uniform capacities) requires $2^{\Omega(k/{\rm poly}\log k)}n^{O(1)}$ time. The first contribution of this paper is to show that CapSoR is APX hard for an explicit factor and even with uniform capacities. That is compared to [58] we removed the ETH assumption, used only uniform capacities, and showed an explicit factor of inapproximability. This is in contrast to the uncapacitated version which is believed to admit a PTAS (assuming $NP\not\subseteq QP$ ).

Theorem 1 (APX-hard).

For every constant $\varepsilon>0$ , it is NP-hard to approximate Uniform CapSoR to within a factor of $(1+1/e-\varepsilon)$ .

Earlier, Bandyapadhyay, Lochet, and Saurabh [11] showed that assuming ETH ${}^{\ref{foot:eth}}$ , no FPT algorithm can solve CapSoR exactly (even with uniform capacities). However, until this point, nothing ruled out the existence of an FPT-Approximation Scheme (FPT-AS) or PAS for Parameterized Approximation Scheme⁸⁸8Such algorithms find $(1+\varepsilon)$ -approximation in time $f(k,\varepsilon)n^{g(\varepsilon)}$ for some fixed functions $f$ and $g$ .. The second contribution of this paper is to show that assuming gap-ETH ${}^{\ref{foot:gapETH}}$ , no such FPT-AS exists.

Theorem 2 (No FPT-AS).

Assuming gap-ETH, for every $\varepsilon>0$ and any function $f$ , there is no $f(k)n^{o(k)}$ time algorithm that approximates Uniform CapSoR to within a factor of $(1+1/e-\varepsilon)$ .

Note that if we allow $n^{O(k)}$ time, then we can exactly solve Sum of Radii using brute-force, even with non-uniform capacities. Therefore, Theorem 2 not only rules out FPT-approximation algorithms for achieving approximation better than factor of $(1+1/e-\varepsilon)$ for this problem, but also implies that the best algorithm in this context essentially is the naive brute-force algorithm, which runs in $n^{O(k)}$ time.

Next, as the best we can hope for is a constant factor approximation in FPT time, we turn to improving this factor. The main result of the paper is a $(3+\sqrt{8}+\varepsilon)\approx 5.83$ FPT-approximation for non-uniform CapSoR, significantly improving the present best [58] factor of $(4+\sqrt{13}+\varepsilon)\approx 7.61$ . The theorem also mentions cluster capacities and other objectives. These will be explained in the following sub-sections.

Theorem 3 (Main Theorem).

There is a (deterministic) FPT-approximation algorithm that finds a $(3+2\sqrt{2}+\varepsilon)$ -approximation for Non-uniform CapSoR for any $\varepsilon>0$ , and runs in time $2^{O(k^{2}\log k+k\log(k/\varepsilon))}n^{O(1)}$ . Furthermore, the algorithm yields $(3+2\sqrt{2}+\varepsilon)$ -approximation for non-uniform capacities even when the objective is a monotone symmetric norm of the radii.
Both results hold also w.r.t. cluster capacities.

Table 1: Summary of our results and previous results for CapSoR and CapSoD. The results for CapSoD are implicit in the corresponding references. Furthermore, CapSoD makes sense only for the cluster capacities. While CapSoR with the

\ell_{\infty}

objective corresponds to the Capacitated

k

-Center problem, CapSoD with the

\ell_{\infty}

objective corresponds to the Capacitated Max-

k

-Diameter problem. While our algorithms are deterministic for non-uniform capacities, the algorithms for the uniform capacity case are randomized. The inapproximability result, assuming gap-ETH, rules out any

f(k)n^{o(k)}

time algorithm that can approximate uniform CapSoR (even with

\ell_{1}

objective) to a factor better than

(1+1/e)

.

Capacities	Norm	Approx. factor	Run time	Ref.
Sum of Radii
		$28$	$2^{O(k^{2})}n^{O(1)}$	[56]
	$\ell_{1}$	$4+\varepsilon$	$2^{O(k\log(k/\varepsilon))}n^{O(1)}$	[11]
Uniform		$3+\varepsilon$
	$\ell_{p}$	$(1+\varepsilon)(2\cdot 4^{p-1}+1)^{1/p}$	$2^{O(k\log(k/\varepsilon))}n^{O(1)}$	[58]
		$(1+\varepsilon)(2\cdot 3^{p-1}+1)^{1/p}$	$2^{O(k^{2}+k\log(k/\varepsilon))}n^{O(1)}$	Theorem 4
	general	$3+\varepsilon$	$2^{O(k^{2}+k\log(k/\varepsilon))}n^{O(1)}$	Theorem 4
(Non-Uni-) Hardness	general	$\beta>1$	$2^{\Omega(k/{\rm polylog}k)}\cdot{\rm poly}(n)$ (ETH)	[58]
		exact	$n^{\Omega(k)}$ (ETH)	[11]
Hardness	general	$(1+1/e-\varepsilon)$	NP-hard	Theorem 1
Uniform		$(1+1/e-\varepsilon)$	$n^{\Omega(k)}$ (gap-ETH)	Theorem 2
	$\ell_{1}$	$15+\varepsilon$	$2^{O(k^{2}\log(k/\varepsilon))}n^{O(1)}$	[11]
Non-Uniform	$\ell_{p}$	$4+\sqrt{13}+\varepsilon\approx 7.61$	$2^{O(k^{3}+k\log(k/\varepsilon))}n^{O(1)}$	[58]
	general	$3+\sqrt{8}+\varepsilon\approx 5.83$	$2^{O(k^{2}\log k+k\log(k/\varepsilon))}n^{O(1)}$	Theorem 3
Sum of Diameters
	$\ell_{1}$	$6+\varepsilon$	$2^{O(k\log(k/\varepsilon))}n^{O(1)}$	[58]
		$4+\varepsilon$	$2^{O(k\log(k/\varepsilon))}n^{O(1)}$	Theorem 5
Uniform	$\ell_{p}$	$(2+\varepsilon)(2\cdot 4^{p-1}+1)^{1/p}$	$2^{O(k\log(k/\varepsilon))}n^{O(1)}$	[58]
		$(2+\varepsilon)(2^{p-1}+1)^{1/p}$	$2^{O(k\log(k/\varepsilon))}n^{O(1)}$	Theorem 5
	general	$4+\varepsilon$	$2^{O(k\log(k/\varepsilon))}n^{O(1)}$	Theorem 5
Non-Uniform	general	$7+\varepsilon$	$2^{O(k^{2}\log k+k\log(k/\varepsilon))}n^{O(1)}$	Theorem 6

1.1 Other norm objectives

In the Sum of Radii problem the goal is to choose $k$ balls covering all the metric points such that the sum of radii $\sum_{i}r_{i}$ is minimized. A natural generalization is to optimize alternate objectives. Specifically, given a norm $\|\cdot\|:\mathbb{R}^{k}\rightarrow\mathbb{R}_{\geq 0}$ , the task is to choose balls covering all metric points so as to minimize the norm of the radii vector $\|(r_{1},\dots,r_{k})\|$ . A canonical example is the $\ell_{p}$ norm where $\|(r_{1},\dots,r_{k})\|_{p}=\left(\sum_{i=1}^{k}r_{i}^{p}\right)^{1/p}$ , which has been studied over two decades [19, 13]. The $\ell_{1}$ norm objective recovers the Sum of Radii problem, while the $\ell_{\infty}$ norm objective ( $\|(r_{1},\dots,r_{k})\|_{\infty}=\max_{i\in[1,k]}r_{i}$ ) corresponds to the classical $k$ -center problem. The other $\ell_{p}$ -norm objectives interpolate between these two fundamental problems in clustering. In particular, they capture objectives such as sum of squared radii,⁹⁹9Sum of squared radii is essentially equivalent to the $\ell_{2}$ objective: an $\alpha$ -approximation algorithm for the $\ell_{2}$ objective yields an $\alpha^{2}$ -approximation to the sum of squared radii. which has received attention in practice, especially in wireless network applications where it naturally models power consumption [4, 65]. This perspective further extends to objectives that impose non-uniform weights on the radii, such as ordered weighted norms or cascaded multi-level $\ell_{p}$ norms. These allow the norm objective to encode heterogeneous priorities or costs across clusters in practical settings [54]. The strength of such generalizations has been recently studied [27, 1], which not only unified the existing FPT-AS for several different problems such as $k$ -median, $k$ -means, and $k$ -center, but also lead to FPT-AS for advanced problems such as priority $k$ -center [48, 10, 72], $\ell$ -centrum [71, 62], ordered $k$ -median [25, 20], and Socially Fair $k$ -median [6, 16, 67, 44], many of which were previously unresolved.

The authors in [58] constructed an algorithm for the uniform capacitated Sum of Radii with $\ell_{p}$ norm of radii with approximation factor $(1+\varepsilon)(2\cdot 4^{p-1}+1)^{1/p}$ in FPT time. In particular, this implies a $(3+\varepsilon)$ FPT-approximation for uniform capacitated Sum of Radii $(p=1)$ and $(4+\varepsilon)$ FPT-approximation ${}^{\ref{footnote:GJ23}}$ for uniform capacitated $k$ -center $(p=\infty)$ . In our work, we generalize and improve these results. Specifically, we obtain a $(3+\varepsilon)$ FPT-approximation w.r.t. any monotone symmetric norm of radii, thus generalizing the $\ell_{p}$ norm objective of [58]. Further, we also improve the approximation ratio for the $\ell_{p}$ norm objective to $(1+\varepsilon)(2\cdot 3^{p-1}+1)^{1/p}$ .

Theorem 4 (Uniform).

There is a randomized algorithm for Uniform CapSoR, oblivious to the objective, that runs in $2^{O(k^{2}+k\log(k/\varepsilon))}n^{O(1)}$ time, and with probability at least $3/5$ returns a solution ${\rm Sol}$ , such that ${\rm Sol}$ is a $(3+\varepsilon)$ -approximation w.r.t. any monotone symmetric norm objective (simultaneously). Furthermore, for $1<p<\infty$ , ${\rm Sol}$ is a $(1+\varepsilon)(2\cdot 3^{p-1}+1)^{1/p}$ -approximation w.r.t. the $\ell_{p}$ norm objective.

For the special case of $p=\infty$ , the $\ell_{\infty}$ norm objective is simply the $k$ -center problem. Here a simple corollary of Theorem 4 implies $(3+\varepsilon)$ FPT-approximation algorithm for $k$ -center with uniform capacities, improving the state of the art factor of $4$ due to [58, 50]. Note that for $p\in(1,\infty]$ , the approximation factor of our Theorem 4 is better than that of [58]. In fact, the approximation factor of our algorithm for $\ell_{p}$ norm objective equals $\max_{\alpha\in[0,1]}\left(\frac{(2+\alpha)^{p}+1}{1+\alpha^{p}}\right)^{% \nicefrac{{1}}{{p}}}$ , which is slightly better than the stated factor. For example, it equals $\approx 2.414$ and $\approx 2.488$ for $p=2$ and $p=3$ , respectively (instead of the stated $\approx 2.65$ and $\approx 2.67$ ). Similarly, [58] explicitly claimed approximation factors of $3$ and $\approx 3.2$ , respectively. However, if we optimize their final expression, it yields factors $\approx 2.92$ and $\approx 3.191$ for $p=2$ and $p=3$ , respectively. See the full version for further discussion.

For non-uniform Capacitated Sum of Radii, [58] obtained approximation factor of $(4+\sqrt{13}+\varepsilon)\approx 7.61$ w.r.t. any $\ell_{p}$ -norm objective in $2^{O(k^{3}+k\log(k/\varepsilon))}n^{O(1)}$ time. As stated in Theorem 3 above, for non-uniform Capacitated Sum of Radii, we obtain approximation factor of $(3+\sqrt{8}+\varepsilon)\approx 5.83$ w.r.t. any monotone symmetric norm objective, in $2^{O(k^{2}\log k+k\log(k/\varepsilon))}n^{O(1)}$ time. Thus we improve over [58] on three fronts (see Table 1): (1) approximation factor, (2) generalizing to any monotone symmetric norm from $\ell_{p}$ norms, and (3) running time.

1.2 Sum of Diameters and cluster capacities

A closely related problem is the Sum of Diameters problem, which has been studied extensively and predates Sum of Radii [51, 52, 70, 26, 40, 28, 14, 40, 43]. Here, the goal is to partition the point set $P$ into $k$ clusters $C_{1},\dots,C_{k}$ , and the objective is to minimize the sum of cluster diameters $\sum_{i=1}^{k}{\rm diam}(C_{i})$ , where the diameter of a cluster is ${\rm diam}(C_{i})=\max_{x,y\in C_{i}}\delta(x,y)$ the maximum pairwise distance between two cluster points. Note that, unlike Sum of Radii, in this problem, there are no centers representing the clusters. Furthermore, this problem is NP-hard to approximate to a factor better than $2$ in polynomial time [40] (unlike Sum of Radii, which admits a QPTAS). A simple observation shows that any $\alpha$ -factor approximation for Sum of Radii implies $2\alpha$ -factor approximation for Sum of Diameters in a black-box way (and vice-versa).¹⁰¹⁰10Given a set of points $P$ , denote by $\mathcal{R}$ and $\mathcal{D}$ the value of the optimal solutions to Sum of Radii and Sum of Diameters respectively. It holds that $\mathcal{R}\leq\mathcal{D}\leq 2\cdot\mathcal{R}$ . Indeed, consider an optimal solution to Sum of Diameters of cost $\mathcal{D}$ , then by picking arbitrary center in each cluster we obtain a solution for Sum of Radii of cost at most $\mathcal{D}$ (thus $\mathcal{R}\leq\mathcal{D}$ ). On the other hand, given a solution to Sum of Radii of cost $\mathcal{R}$ , the clusters induced by the balls constitute a solution to Sum of Diameters of cost at most $2\cdot\mathcal{R}$ (thus $\mathcal{D}\leq 2\cdot\mathcal{R}$ ). This trick has often been used to design approximation algorithms for Sum of Diameters. In fact, the current state-of-the-art algorithms for Sum of Diameters, including a polynomial-time $(6+\varepsilon)$ -approximation [21] and a quasi-polynomial-time $(2+\varepsilon)$ -approximation [45], are based on this implicit trick by applying it to the polynomial-time $(3+\varepsilon)$ -approximation and QPTAS for Sum of Radii, respectively.

Capacitated Sum of Diameters

We introduce the problem of Capacitated Sum of Diameters (CapSoD). Here we are initially given $k$ capacities $U_{1},\dots,U_{k}$ , the goal is to partition the point set $P$ into $k$ clusters $C_{1},\dots,C_{k}$ , such that for every $i$ , $|C_{i}|\leq U_{i}$ , while the objective is to minimize the sum of cluster diameters. We call the capacities uniform if all the capacities are equal $U_{1}=\dots=U_{k}$ , and non-uniform otherwise. Under uniform capacities, the reduction mentioned in Footnote 10 goes through. Thus an $\alpha$ approximation algorithm to uniform capacitated Sum of Radii transfers in a black-box manner into a $2\alpha$ approximation algorithm for the uniform capacitated Sum of Diameters, with the same running time. In particular, by using [58], one can obtain a $6+\varepsilon$ -approximation for uniform capacitated Sum of Diameters in FPT time. In fact, similarly to Sum of Radii, one can study Capacitated Sum of Diameters w.r.t. any norm objective, and the reduction will still go through. Thus it follows from [58] that for any $\ell_{p}$ norm objective, uniform capacitated Sum of Diameters admits $2(1+\varepsilon)(4^{p-1}+1)^{1/p}$ FPT approximation. Similarly, using our Theorem 4, we can obtain FPT time $6+\varepsilon$ approximation for uniform capacitated Sum of Diameters w.r.t. to any monotone symmetric norm, or $2(1+\varepsilon)(3^{p-1}+1)^{1/p}$ -approximation w.r.t. $\ell_{p}$ norm objective. Sum of Diameters is a fundamental and important problem. Its capacitated version was not previously explicitly studied simply because there was nothing to say beyond this simple reduction.

In our work, we go beyond this reduction and directly design novel approximation algorithms for capacitated Sum of Diameters with significantly better approximation factors than twice that of Sum of Radii.

Theorem 5 (Uniform Diameters).

There is a randomized algorithm that given an instance of the Uniform CapSoD runs in $2^{O(k\log(k/\varepsilon))}n^{O(1)}$ time, and with probability at least $3/5$ returns a solution ${\rm Sol}$ , such that ${\rm Sol}$ is a $(4+\varepsilon)$ -approximation w.r.t. any monotone symmetric norm objective (simultaneously). Furthermore, for $1<p<\infty$ , ${\rm Sol}$ is a $(2+\varepsilon)(2^{p-1}+1)^{1/p}$ -approximation w.r.t. the $\ell_{p}$ norm objective.

Finally, we proceed to consider the more challenging problem of non-uniform Capacitated Sum of Diameters. Here we obtain a $7+\varepsilon$ approximation w.r.t. to any monotone symmetric norm objective.

Theorem 6 (Non-Uniform Diameters).

For any $\varepsilon>0$ , there is a (deterministic) algorithm running $2^{O(k^{2}+k\log(k/\varepsilon))}n^{O(1)}$ -time and returns a $(7+\varepsilon)$ -approximation for Non-uniform CapSoD w.r.t. any monotone symmetric norm objective.

Cluster capacities

Bandyapadhyay, Lochet, and Saurabh [11] introduced the problem of Capacitated Sum of Radii where each point $p\in P$ has a capacity $U_{p}$ , and a cluster centered in $p$ can contain at most $U_{p}$ points. This corresponds for example to a scenario where we want to construct water wells, and a well constructed at point $p$ can serve up to $U_{p}$ clients. However, an equally natural problem is where one is given $k$ capacities $U_{1},\dots,U_{k}$ , and the goal is to construct $k$ clusters with arbitrary centers, such that the $i$ ’th cluster contains at most $U_{i}$ points. This problem is similar to our capacitated Sum of Diameters, and can correspond to a scenario where one wants to distribute already existing $k$ water tanks (for example in a tent village during a festival). We refer to the two versions of the problem as node capacities, and cluster capacities, respectively. Note that for uniform capacities the two versions coincide. Further, note that the reduction from Sum of Radii to Sum of Diameters mentioned in Footnote 10 holds in the capacitated version w.r.t. cluster capacities. Our results on node capacities in Theorem 3 hold for cluster capacities as well ( $3+2\sqrt{2}+\varepsilon$ approximation for any monotone symmetric norm objective). No results on Sum of Radii with non-uniform cluster capacities were previously known.

Organization. Due to space constraints, we defer all algorithms and technical proofs to the full version. In the next section, we outline the main technical ideas behind our results.

2 Overview of techniques

In this section, we highlight our conceptual and technical contributions. Due to space constraints, we begin with our main theorem (Theorem 3) and present the key ideas behind our algorithm for non-uniform capacities in Section 2.1. Then, in Section 2.2, we delve into the algorithmic ideas for uniform capacities. Note however, that from a pedagogical viewpoint, it is easier to begin reading first Section 2.2, followed by Section 2.1. We now set up basic notations required for the exposition.

Notations. We denote by $\mathcal{I}$ an instance of capacitated Sum of Radii or capacitated Sum of Diameters, depending upon the context. For uniform capacities, $\mathcal{I}$ consists of metric space $(P,\delta)$ , a positive integer $k$ , and a uniform capacity $U>0$ . The elements in $P$ are called points. For non-uniform node capacities, $U$ is replaced by corresponding node capacities $\{U_{p}\}_{p\in P}$ , and for non-uniform cluster capacities, $U$ is replaced by corresponding cluster capacities $\{U_{1},\cdots,U_{k}\}$ . We denote by $\mathcal{C}=\{C_{1},\cdots,C_{k}\}$ an optimal (but fixed) clustering for $\mathcal{I}$ . For ease of analysis, we assume that $|\mathcal{C}|=k$ , otherwise, we can add zero radius clusters to make it $k$ , without increasing the cost of $\mathcal{I}$ . Note that the clusters in $\mathcal{C}$ are disjoint. When $\mathcal{I}$ is an instance of capacitated Sum of Radii, we denote by $r^{*}_{i}$ and $o_{i}$ as the radius and the center of cluster $C_{i}\in\mathcal{C}$ , respectively, and let $O=\{o_{1},\cdots,o_{k}\}$ . In this case, we let $\text{OPT}=r^{*}_{1}+\cdots+r^{*}_{k}$ . When $\mathcal{I}$ is an instance of capacitated Sum of Diameters, we denote by $d^{*}_{i}$ as the diameter of cluster $C_{i}\in\mathcal{C}$ . In this case, we let $\text{OPT}=d^{*}_{1}+\cdots+d^{*}_{k}$ . It is known that we can guess in FPT time in $k$ , a set ( $\varepsilon$ -approximation) $\{r_{1},\cdots,r_{k}\}$ corresponding to $\{r^{*}_{1},\cdots,r^{*}_{k}\}$ such that $\sum_{i\in[k]}r_{i}\leq(1+\varepsilon)\cdot\sum_{i\in[k]}r^{*}_{i}$ and $r_{i}\geq r^{*}_{i}$ . Similarly, let $\{d_{1},\cdots,d_{k}\}$ denote $\varepsilon$ -approximation of $\{d^{*}_{1},\cdots,d^{*}_{k}\}$ . A feasible solution to $\mathcal{I}$ is a partition of $P$ (along with centers for Sum of Radii) such that the capacities are respected. For a point $p\in P$ and a positive real $r$ , denote by ${\sf ball}(p,r)$ as the set of points from $P$ that are at a distance at most $r$ from $p$ .

$\blacktriangleright$ Remark 7 (Point assignment using matching and flows).

In this section (and throughout the paper), we will focus on presenting a set of centers and their corresponding radii as our solution. This approach suffices because, given such a set of centers and radii, we can determine in polynomial time whether there exists a corresponding feasible solution (i.e., feasible assignment of points to the centers/clusters) with the same cost. Moreover, we can also find such a solution by defining an appropriate flow problem (see the full version).

$\blacktriangleright$ Remark 8 (FPT and bounded guessing).

We assume that our algorithms have a power to make ${\rm poly}(k)$ guesses each with success probability $p(k)$ . Such algorithms can be transformed into a randomized FPT algorithms that are correct with constant probability. See the full version for more details.

2.1 Non-uniform capacitated Sum of Radii

For ease of exposition, in this technical overview we highlight our ideas for cluster capacities (see paragraph 1.2). Transitioning to node capacities introduces several more challenges which we will not discuss here. Other than the basic FPT framework mentioned in the preliminaries above, our algorithm is fundamentally different from these of [11, 58], and hence we do not attempt to compare them (in contrast, for uniform capacities the algorithms are similar).

Consider the following simple and natural strategy of processing clusters in $\mathcal{C}$ iteratively (see the full version for pseudo-code). Initially all the clusters in $\mathcal{C}$ are unprocessed (colored red). We will process the clusters in $\mathcal{C}$ in non-decreasing order of their radii, denoted as $C_{1},\cdots,C_{k}$ . Let $U_{1},\cdots,U_{k}$ be the corresponding cluster capacities. Consider the first iteration when we process $C_{1}$ . Suppose we could find a dense ball $D_{1}={\sf ball}(y_{1},r_{1})$ of radius $r_{1}$ in $P$ such that $|D_{1}|\geq|C_{1}|$ . Then, we could create a cluster $C^{\prime}_{1}\subseteq D_{1}$ of size $|C_{1}|$ ¹¹¹¹11Even though $|C_{1}|$ is unknown, in retrospect, we will be able to use Remark 7 to obtain such a clustering. with radius $r_{1}$ , matching the optimal cost. To make this cluster permanent, we delete the points from $D_{1}$ to prevent them from being reassigned in later iterations. However, this could create problems – (i) $C^{\prime}_{1}$ may contain points from other clusters, so in the future iterations when we process these clusters then the densest ball may not have enough points, and (ii) we need to make sure the points of $C_{1}$ are taken care by some cluster in our solution. Our algorithm is based on the following two key ideas that handle these two issues:

Invariant: do not touch the unprocessed.

We ensure that, throughout the algorithm, every unprocessed cluster in $\mathcal{C}$ has all of its points intact. In other words, during the processing iteration of $C_{i}$ , all its points are present.

Making progress: Good dense balls.

An immediate implication of the above invariant is that when we process $C_{i}$ , there is a ball of radius $r_{i}$ containing at least $|C_{i}|$ points. Let $D_{i}={\sf ball}(y_{i},r_{i})$ be the densest ball w.r.t. the remaining points during the iteration of $C_{i}$ . Note that such a ball contains at least $|C_{i}|$ points due to the above invariant. Consider the smallest radius cluster $C_{j}\in\mathcal{C}$ that intersects $D_{i}$ , and call $C_{j}$ the anchor for $D_{i}$ . See top-left figure in Figure 3, where $D_{i}$ is the ball centered at $y$ with radius $r_{i}$ , $C_{i}=C_{5}$ and $C_{j}=C_{8}$ . Now, consider the extended ball $D^{\prime}_{i}:={\sf ball}(y_{i},r_{i}+2r_{j})$ , and note that $C_{j}\subseteq D^{\prime}_{i}$ . Now, if $C_{i}$ intersects $D^{\prime}_{i}$ , then $C_{i}$ is not far from $y_{i}$ (see top-right figure in Figure 3). In this case, we call $D_{i}$ a good dense ball, and will be able to process $C_{i}$ . Thus, our first goal when processing the cluster $C_{i}$ is to find a good dense ball.

Finding good dense ball in FPT time. Suppose $D^{\prime}_{i}$ does not intersect $C_{i}$ , then we can temporarily delete $D^{\prime}_{i}={\sf ball}(y_{i},r_{i}+2r_{j})$ since this ball does not contain any point of $C_{i}$ (see top-left figure in Figure 3, where $C_{i}=C_{5}$ and $C_{j}=C_{8}$ ). Furthermore, we end up deleting at least one cluster (specifically, $C_{j}$ ), so this process of temporarily deleting balls can repeat at most $k$ times before $C_{i}$ intersects the extended ball $D^{\prime}_{i}$ . Once we have a good dense ball $D_{i}={\sf ball}(y_{i},r_{i})$ for $C_{i}$ , consider the extended ball $D^{\prime}_{i}:={\sf ball}(y_{i},r_{i}+2r_{j})$ , where $r_{j}$ is the radius of the anchor $C_{j}$ for $D_{i}$ . There are two cases:

Case $1$ : Hop through the anchors. Suppose we are lucky, and it turns out that $r_{j}\leq r_{i}$ . Then, $y_{i}$ can serve all the points of $C_{i}$ within radius $3r_{i}+2r_{j}\leq 5r_{i}$ . See top-right figure in Figure 3, where $C_{j}=C_{3}$ . We now mark $C_{i}$ as processed (color black). Note that, in this case, we do not delete any points.

Case $2$ : Otherwise “Exchange”. Suppose we are not lucky, and it turns out that $r_{j}>r_{i}$ (see bottom-left figure in Figure 3 where $r_{i}=r_{5}>r_{8}=r_{j}$ ). In this case, our basic approach is to open the cluster $C_{i}$ at $D_{i}$ , and thus relieving the clusters intersecting $D_{i}$ from their responsibility for these points. In exchange, these clusters will become responsible for $C_{i}$ points. The crux of the argument is that as the anchor $C_{j}$ has the minimal radius among the clusters intersecting $D_{i}$ , each such cluster $C_{q}$ has radius larger than $r_{i}$ . Thus from $C_{q}$ ’s perspective, the points of $C_{i}$ are “nearby”. Hence $C_{q}$ can accept responsibility for a number of $C_{i}$ points proportional to the number of $C_{q}$ points taken (and thus everybody is taken care of).

In more details: we create a new cluster $C^{\prime}_{i}\subseteq D_{i}$ out of the points in $D_{i}$ (recall $|D_{i}|\geq|C_{i}|$ and see Footnote 11). To make this assignment permanent, we delete $D_{i}$ , and mark $C_{i}$ as processed (color black). However, we end up taking points from other clusters (and also end up deleting points from these clusters). The key observation is that as we process the clusters in non-decreasing order and $r_{j}>r_{i}$ , $D_{i}$ does not contain points from clusters processed via Case $1$ . Since we maintain the invariant that the points of unprocessed clusters are not deleted, we have to mark the clusters intersecting $D_{i}$ as processed (color black). However, before marking these clusters as processed, we need to ensure that they are accounted for in our solution. To this end, we use a novel idea of exchanging points. Since we have created a new cluster $C^{\prime}_{i}$ out of $D_{i}$ , any cluster $C_{j^{\prime}}$ that has lost, say, $n_{j^{\prime}}>0$ points in this process, can instead claim back $n_{j^{\prime}}$ points from the original cluster $C_{i}$ (depicted by islands in $C_{5}$ in bottom-left figure in Figure 3) by paying slightly more cost since, in this case, we have $r_{i}<r_{j}\leq r_{j^{\prime}}$ . Here, we use the fact that $C_{j}$ is the anchor for $D_{i}$ , and hence $r_{j}$ is the smallest radius intersecting $D_{i}$ . We call such clusters partitioned clusters. Specifically, the radius of the partitioned $C_{j^{\prime}}$ is at most $\delta(o_{j^{\prime}},y_{i})+\delta(y_{i},p)\leq(r_{j^{\prime}}+r_{i})+(r_{i}+% 2r_{j}+2r_{i})\leq 7r_{j^{\prime}}$ , for $p\in C_{i}$ , as $r_{j}\leq r_{j^{\prime}}$ . See bottom-left figure in for an illustration. Note that a cluster $C_{j^{\prime}}$ can be partitioned multiple times by different $C_{i}$ ’s (we track the clusters that partitioned $C_{j^{\prime}}$ by ${\textsf{Partitions-of}}(C_{j^{\prime}})$ ), as shown in bottom-right figure in Figure 3. However, $o_{j^{\prime}}$ can still serve all the points of the modified $C_{j^{\prime}}$ within cost $7r_{j^{\prime}}$ , since, in this case, the radii of the clusters partitioning $C_{j^{\prime}}$ are strictly less than $r_{j^{\prime}}$ . While it is hard to find $o_{j^{\prime}}$ , in the full version, we show how to find another point that can serve all the points of the partitioned cluster $C_{j^{\prime}}$ within radius $7r_{j^{\prime}}$ .

Note that, we get different approximation factors in Case $1$ and Case $2$ . In the technical section, we interpolate between these two factors to obtain an improved approximation factor for the algorithm.

2.2 Uniform capacities

Our algorithm builds upon the algorithm of [58]. The algorithm divides the clusters in $\mathcal{C}$ into two categories: heavy and light. A cluster $C\in\mathcal{C}$ is heavy if $|C|>\nicefrac{{U}}{{k^{3}}}$ ; otherwise, it is a light cluster. The intuition behind this partition is the following: some heavy cluster must exist, and given such heavy cluster $C\in\mathcal{C}$ , a randomly selected point from $P$ belongs to $C$ with probability at least ${\rm poly}(1/k)$ . Therefore, with probability at least $k^{-O(k)}$ , we can obtain a set $X\subseteq P$ containing a single point $x_{i}$ from every heavy cluster $C_{i}\in\mathcal{C}$ . For every heavy cluster $C_{i}$ , we wish to open a cluster $B_{i}={\sf ball}(x_{i},2r_{i})$ that will take care of $C_{i}$ points (note $C_{i}\subseteq B_{i}$ ). We will assume that the union of these balls, $\cup_{x_{i}\in X}B_{i}$ , covers the point set $P$ (this assumption catches the essence of the problem, as we can greedily take care of light clusters not covered by this union). Let $\mathcal{L}\subseteq P$ be the set of points corresponding to the light clusters in $\mathcal{C}$ . For each light cluster $C_{t}\in\mathcal{C}$ , arbitrarily assign it to a heavy cluster $C_{i}\in\mathcal{C}$ such that $C_{t}$ intersects $B_{i}$ . Then, for each heavy cluster $C_{i}$ , consider the set $S_{i}:=C_{i}\cup({\sf ball}(x_{i},2r_{i}+2r_{\ell(i)})\cap\mathcal{L})$ , where $r_{\ell(i)}$ is the maximum radius of a light cluster assigned to $C_{i}$ . Note that $S_{i}$ contains $C_{i}$ , and all the light clusters assigned to $C_{i}$ . If $|S_{i}|\leq U$ , then we can open cluster $C^{\prime}_{i}=S_{i}$ without violating the uniform capacity. For the other case, note that $|S_{i}|\leq(1+\nicefrac{{1}}{{k^{2}}})U$ since there can be at most $k$ light clusters assigned to $C_{i}$ , each of which has at most $U/k^{3}$ points. Let $I\subseteq[k]$ be the indices of heavy clusters, and let $I^{\prime}\subseteq I$ be the indices of heavy clusters for whom $S_{i}$ violated the capacity constraint. [58] used a very neat matching based argument to construct $|I^{\prime}|$ balls $\{\hat{C}_{i}\}_{i\in I^{\prime}}$ each with a unique radius from $\{r_{i}\}_{i\in I}$ (the heavy clusters) such that $\cup_{i\in I^{\prime}}\hat{C}_{i}$ contains at least $\nicefrac{{U}}{{k^{2}}}$ points from each $S_{i}$ (for $i\in I^{\prime}$ ). These clusters $\{\hat{C}_{i}\}_{i\in I^{\prime}}$ are then used to unload enough points from the overloaded heavy clusters. Now, $\{{\sf ball}(x_{i},2r_{i}+2r_{\ell(i)})\}_{i\in I}$ together with $\{\hat{C}_{i}\}_{i\in I^{\prime}}$ is a valid feasible solution. The $\ell_{1}$ norm cost (CapSoR cost) of this solution is bounded by $\sum_{i\in I}(2r_{i}+2r_{\ell(i)})+\sum_{j\in I}r_{j}\leq 3\sum_{i\in[k]}r_{i}% \leq(3+\varepsilon){\rm OPT},$ where we used that fact that $C_{\ell(i)}$ is distinct for each $C_{i}$ , and that in $\cup_{i\in I^{\prime}}\hat{C}_{i}$ we used the radius of every heavy cluster at most once. On the other hand, the $\ell_{\infty}$ cost (Capacitated $k$ -Center) can only be bounded by $(4+\varepsilon){\rm OPT}$ . It is also possible to bound the approximation factor for general $\ell_{p}$ norm objective.

Improvement for $\ell_{p}$ norm objectives

Our modification to get a better factor is very small, but leads to a significant improvement. Specifically, we fine tune the definition of $C_{\ell(i)}$ for $C_{i}$ .

Figure 2: The sampled point

x_{i}

belongs to the heavy cluster,

C_{i}

.

[58] assigned each light cluster $C_{j}$ to an arbitrary heavy cluster $C_{i}$ such that $C_{j}$ intersects the extended ball $B_{i}$ , and let $r_{\ell(i)}$ to be the maximum radius of a light cluster assigned to $C_{i}$ . Instead, we assign each light cluster $C_{j}$ to an arbitrary heavy cluster $C_{i}$ such that $B_{i}$ contains its center $o_{i}$ , while $r_{\ell(i)}$ remains the maximum radius of a light cluster assigned to $C_{i}$ . The crux is that now the ball ${\sf ball}(x_{i},2r_{i}+r_{\ell(i)})$ contains the heavy cluster $C_{i}$ and all the light clusters assigned to it. In the example shown in Figure 2, we consider a heavy cluster $C_{i}$ , where we sampled a point $x_{i}\in C_{i}$ and consider the ball $B_{i}={\sf ball}(x_{i},2r_{i})$ . $B_{i}$ intersects $3$ light clusters ( $C_{1},C_{2},C_{3}$ ) with radii $r_{1}<r_{2}<r_{3}$ . Now $r_{\ell(i)}=r_{2}$ because $o_{2}\in B_{i}$ , while $o_{3}\notin B_{i}$ . As previously, we open clusters of two types: (1) for every heavy cluster $C_{i}$ , a cluster $C^{\prime}_{i}$ centered at $x_{i}$ of radius $2r_{i}+r_{\ell(i)}$ , and (2) the clusters $\{\hat{C}\}_{i\in I^{\prime}}$ relieving the extra load. Overall, we save a factor of $r_{\ell(i)}$ in the radius of the cluster centered at $x_{i}$ . Note that this solution yields a $3$ approximation w.r.t. the $\ell_{\infty}$ norm objective (Capacitated $k$ -Center), and yields a similar improvement w.r.t. other $\ell_{p}$ norm objectives.

2.3 Hardness of FPT-approximation for uniform capacities

Our hardness result is based on a polynomial time reduction from Max $k$ -Coverage (Max $k$ -Cov), where, given a universe $\mathcal{G}$ of elements, a positive integer $k$ , and $k$ collections $\{\mathcal{C}_{1},\dots,\mathcal{C}_{k}\}$ of subsets of $G$ , the task is to find $\{S_{1},\dots,S_{k}\}$ such that $S_{i}\in\mathcal{C}_{i},i\in[k]$ that maximizes the number of elements covered. It is known that Max $k$ -Cov is NP-hard to approximate to a factor better than $(1-1/e)$ , even when every set in the collection has precisely $|\mathcal{G}|/k$ elements. Under gap-ETH, there is no $\textsf{FPT}(k)$ algorithm for Max $k$ -Cov that approximates to a factor better than $(1-1/e)$ , even when every set in the collection has precisely $|\mathcal{G}|/k$ elements

On a high level, given an instance of Max $k$ -Cov, we create the set-element incidence graph of the instance. We then add edges between the vertices corresponding to the sets of the same collection. Let $G=(V,E)$ be the resulting graph. The points of our CapSoR instance corresponds to the vertices in $V$ , and the distance metric is given by the shortest path distance in $G$ . Finally, we set the uniform capacity $U=|\mathcal{G}|/k+m$ . It is easy to see that when there are $k$ sets $\{S_{1},\dots,S_{k}\}$ such that $S_{i}\in\mathcal{C}_{i},i\in[k]$ that cover $\mathcal{G}$ , then we can find a solution for CapSoR with cost $k$ , by selecting the points corresponding to the sets $\{S_{1},\dots,S_{k}\}$ as the centers. For the No case, observe that any solution to CapSoR must have clusters of size precisely $U$ due to our construction. This simple observation forces the centers to belong to different collections, yielding the result.

Figure 3: Top-Left figure shows a dense ball

{\sf ball}(y,r_{5})

, colored in black, that is not good for cluster

C_{5}

, because

{\sf ball}(y,r_{5}+2r_{8})

is disjoint from

C_{5}

. Hence, it is safe to (temporary) delete

{\sf ball}(y,r_{5}+2r_{8})

without affecting cluster

C_{5}

, and recursively search for good dense ball for

C_{5}

in the remaining points. On the other hand, the

{\sf ball}(y,r_{5})

of Top-Right figure is good dense ball for

C_{5}

. Furthermore, note that in this case the radius of the anchor

r_{3}\leq r_{5}

, and hence

y

can serve all the points of

C_{5}

within distance

3r_{5}+2r_{3}\leq 5r_{5}

. In Bottom-left figure, the radius of the anchor is

r_{8}>r_{5}

, and hence the previous argument fails. However, in this case, since

{\sf ball}(y_{,}r_{5})

is a good dense ball for

C_{5}

, so we can open a new cluster

C^{\prime}_{5}\subseteq{\sf ball}(y,r_{5})

of appropriate size, instead of serving the points of

C_{5}

. Note that, in this case, the new cluster

C^{\prime}_{5}

ends up taking points from clusters

C_{8},C_{9}

and

C_{10}

. However, these clusters can claim back the lost points from the original cluster

C_{5}

(depicted by islands in

C_{5}

), which is not too far from them. In this case, we say that

C_{8},C_{9}

and

C_{10}

are partitioned by

C^{\prime}_{5}

. Bottom-right figure shows cluster

C_{8}

partitioned by

C_{2},C_{4}

and

C_{5}

, and it has to collect its lost points from the respective clusters.

3 Further related work

We begin with further background on the (uncapacitated) Sum of Radii and Sum of Diameters problems. When the point set $P$ is from either $\ell_{1}$ or $\ell_{2}$ there is an exact poly-time algorithm [45], while there is also an EPTAS for the Euclidean ( $\ell_{2}$ ) case [45]. Another interesting case is when the metric between the input points $P$ corresponds to the shortest path metric of an unweighted graph $G$ . Here, assuming the optimal solution does not contain singletons (clusters with only a single point), there is a polynomial time algorithm finding optimal solution [14]. The Sum of Diameters with fixed $k$ admits exact polytime algorithm [14] (see also [51, 26]). Further, there is a PTAS for Sum of Diameters where the input points are from the Euclidean plane [14]. The Sum of Radii problem was also studied in the fault tolerant regime [17], considering outliers [3], and in an online (competitive analysis) setting [42, 36].

Capacitated $k$ -Center is a special case of capacitated $\ell_{p}$ norm of radii when $p=\infty$ . The uniform Capacitated $k$ -Center problem has been explicitly studied by Goyal and Jaiswal [50], and is also implicitly captured by the results of [58]. Goyal and Jaiswal design a factor $2$ FPT-approximation for the soft assignment setting, where multiple centers can be opened at a single point, enabling it to serve more than $U$ points. For instance, the algorithm can opt to open two centers at a point $p\in P$ , thereby allowing up to $2U$ points to be served from location $p$ . In contrast, similar to this paper, [58] focus on the hard assignment scenario, where at most one center can be opened at a given point, and they present a $(4+\varepsilon)$ FPT-approximation for this case. We are not aware of any approximation preserving subroutines that transform a soft assignment algorithm to a hard assignment algorithm. However, by replacing the chosen center with any other point in the cluster one can obtain a solution with hard assignments while incurring a factor $2$ multiplicative loss in approximation. Consequently, the algorithm of [50] can only yield $4$ FPT-approximation using this approach, which matches the factor of [58].

Capacitated Max- $k$ -Diameter is a special case of capacitated $\ell_{p}$ norm of diameters problem when $p=\infty$ . Its uncapacitated version turns out to be computationally very challenging. While there is a simple $2$ -approximation for Max- $k$ -Diameter [47], it is NP-hard to approximate the problem better than factor $2$ in $\ell_{\infty}$ metric even for $k=3$ [69]. Very recently, Fleischmann [41] showed that, even for $k=3$ , the problem is NP-hard to approximate better than factors $1.5$ and $1.304$ when the points come from $\ell_{1}$ and $\ell_{2}$ metrics, respectively. Given that these hardness results hold for constant $k$ (i.e., even for $k=3$ ), they also translate to FPT lower bounds. Thus, these hardness results imply that no FPT algorithm can beat these lower bounds for Max- $k$ -Diameter, unless $\textsf{P}=\textsf{NP}$ . Of course, the corresponding capacitated version of Max- $k$ -Diameter is a generalization of Max- $k$ -Diameter, and hence these FPT-hardness of approximations also hold for the capacitated version. For upper bounds, it is interesting to note that the reduction from Sum of Radii to Sum of Diameters mentioned in Footnote 10 works even when solving Sum of Radii w.r.t. soft assignments. Thus using [50] one can obtain a $4$ FPT-approximation for the uniform Capacitated Max- $k$ -Diameter problem, matching our Theorem 5 for this case.

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 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1377–1399, 2023. doi:10.1109/FOCS57990.2023.00085.
[2] Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlodarczyk. Constant-factor FPT approximation for capacitated k-median. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 1:1–1:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ESA.2019.1.
[3] 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, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 69:1–69:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.69.
[4] Helmut Alt, Esther M Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P Fekete, Christian Knauer, Jonathan Lenchner, Joseph SB Mitchell, and Kim Whittlesey. Minimum-cost coverage of point sets by disks. In Proceedings of the twenty-second annual symposium on Computational geometry, pages 449–458, 2006.
[5] Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. Math. Program., 154(1-2):29–53, 2015. doi:10.1007/S10107-014-0857-Y.
[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):pages 79–101, 2010.
[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 J. Comput., 33(3):544–562, 2004. doi:10.1137/S0097539702416402.
[8] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The Hardness of Approximation of Euclidean k-Means. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry (SoCG 2015), volume 34 of Leibniz International Proceedings in Informatics (LIPIcs), pages 754–767, Dagstuhl, Germany, 2015. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SOCG.2015.754.
[9] Mihai Badŏiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In John H. Reif, editor, Proc. 34th Annual ACM Symposium on Theory of Computing (STOC’02), pages 250–257. ACM, 2002. doi:10.1145/509907.509947.
[10] Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, and Maryam Negahbani. Revisiting Priority k-Center: Fairness and Outliers. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.21.
[11] 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), volume 258 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:14, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2023.12.
[12] Sayan Bandyapadhyay and Kasturi R. Varadarajan. Approximate clustering via metric partitioning. In Seok-Hee Hong, editor, 27th International Symposium on Algorithms and Computation, ISAAC 2016, December 12-14, 2016, Sydney, Australia, volume 64 of LIPIcs, pages 15:1–15:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ISAAC.2016.15.
[13] Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav. Novel properties of hierarchical probabilistic partitions and their algorithmic applications. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1724–1767, 2024. doi:10.1109/FOCS61266.2024.00107.
[14] Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and diameters clustering. Algorithmica, 73(1):143–165, 2015. doi:10.1007/S00453-014-9907-3.
[15] Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained $k$ -means problem. Theory of Computing Systems, 62(1):93–115, 2018. doi:10.1007/S00224-017-9820-7.
[16] Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann. New approximability results for the robust $k$ -median problem. In Scandinavian Workshop on Algorithm Theory (SWAT’14), pages 50–61. Springer, 2014. doi:10.1007/978-3-319-08404-6_5.
[17] Santanu Bhowmick, Tanmay Inamdar, and Kasturi R. Varadarajan. Fault-tolerant covering problems in metric spaces. Algorithmica, 83(2):413–446, 2021. doi:10.1007/S00453-020-00762-Y.
[18] Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Geometric clustering to minimize the sum of cluster sizes. In Gerth Stølting Brodal and Stefano Leonardi, editors, Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, volume 3669 of Lecture Notes in Computer Science, pages 460–471. Springer, 2005. doi:10.1007/11561071_42.
[19] Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Geometric clustering to minimize the sum of cluster sizes. In Gerth Stølting Brodal and Stefano Leonardi, editors, Algorithms – ESA 2005, pages 460–471, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/11561071_42.
[20] Vladimir Braverman, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for ordered weighted clustering. In International Conference on Machine Learning (ICML’19), pages 744–753. PMLR, 2019. URL: http://proceedings.mlr.press/v97/braverman19a.html.
[21] Moritz Buchem, Katja Ettmayr, Hugo K. K. Rosado, and Andreas Wiese. A (3 + $\varepsilon$ )-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1738–1765. SIAM, 2024. doi:10.1137/1.9781611977912.69.
[22] Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitated k-median problems. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 722–736. SIAM, 2015. doi:10.1137/1.9781611973730.49.
[23] Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms, 13(2):23:1–23:31, 2017. doi:10.1145/2981561.
[24] Jaroslaw Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform capacitated k-median problem with 1+\epsilon capacity violation. In Quentin Louveaux and Martin Skutella, editors, Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, volume 9682 of Lecture Notes in Computer Science, pages 262–274. Springer, 2016. doi:10.1007/978-3-319-33461-5_22.
[25] Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase. Constant-factor approximation for ordered k median. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18), pages 620–631, 2018. doi:10.1145/3188745.3188930.
[26] Vasilis Capoyleas, Günter Rote, and Gerhard J. Woeginger. Geometric clusterings. J. Algorithms, 12(2):341–356, 1991. doi:10.1016/0196-6774(91)90007-L.
[27] Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 126–137, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3313276.3316322.
[28] Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. Journal of Computer and System Sciences, 68(2):417–441, 2004. Special Issue on STOC 2001. doi:10.1016/j.jcss.2003.07.014.
[29] Xianrun Chen, Dachuan Xu, Yicheng Xu, and Yong Zhang. Parameterized approximation algorithms for sum of radii clustering and variants. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors, Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada, pages 20666–20673. AAAI Press, 2024. doi:10.1609/AAAI.V38I18.30053.
[30] Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 952–958. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070569.
[31] Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm for k-median. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1556–1612. SIAM, 2022. doi:10.1137/1.9781611977073.65.
[32] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.
[33] Vincent Cohen-Addad and Karthik C. S. Inapproximability of clustering in lp metrics. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 519–539. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00040.
[34] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. Johnson coverage hypothesis: Inapproximability of $k$ -means and $k$ -median in ${\ell}_{p}$ -metrics. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1493–1530. SIAM, 2022. doi:10.1137/1.9781611977073.63.
[35] Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1–41:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.41.
[36] János Csirik, Leah Epstein, Csanád Imreh, and Asaf Levin. Online clustering with variable sized clusters. Algorithmica, 65(2):251–274, 2013. doi:10.1007/S00453-011-9586-2.
[37] Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 273–282. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.63.
[38] Sanjoy Dasgupta. The hardness of $k$ -means clustering. Technical Report CS2008-0916, University of California, San Diego, San Diego, CA, 2008.
[39] H. Gökalp Demirci and Shi Li. Constant approximation for capacitated k-median with (1+epsilon)-capacity violation. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 73:1–73:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.73.
[40] Srinivas Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor, and Peter Widmayer. Approximation algorithms for clustering to minimize the sum of diameters. Nordic J. of Computing, 7(3):185–203, September 2000.
[41] Henry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, and Stepan Zharkov. Inapproximability of maximum diameter clustering for few clusters. CoRR, abs/2312.02097, 2023. doi:10.48550/arXiv.2312.02097.
[42] Dimitris Fotakis and Paraschos Koutris. Online sum-radii clustering. Theor. Comput. Sci., 540:27–39, 2014. doi:10.1016/J.TCS.2013.03.010.
[43] 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), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1–56:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2022.56.
[44] Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair $k$ -means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 438–448, 2021. doi:10.1145/3442188.3445906.
[45] Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan. On metric clustering to minimize the sum of radii. Algorithmica, 57(3):484–498, July 2010. doi:10.1007/S00453-009-9282-7.
[46] 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.
[47] 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.
[48] Inge Li Gørtz and Anthony Wirth. Asymmetry in k-center variants. Theor. Comput. Sci., 361(2-3):188–199, 2006. doi:10.1016/J.TCS.2006.05.009.
[49] Kishen N. Gowda, Thomas W. Pensyl, Aravind Srinivasan, and Khoa Trinh. Improved bi-point rounding algorithms and a golden barrier for k-median. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 987–1011. SIAM, 2023. doi:10.1137/1.9781611977554.CH38.
[50] Dishant Goyal and Ragesh Jaiswal. Tight fpt approximation for constrained k-center and k-supplier. Theoretical Computer Science, 940:190–208, 2023. doi:10.1016/j.tcs.2022.11.001.
[51] Pierre Hansen and Brigitte Jaumard. Minimum sum of diameters clustering. Journal of Classification, 4(2):215–226, 1987.
[52] Pierre Hansen and Brigitte Jaumard. Cluster analysis and mathematical programming. Math. Program., 79:191–215, 1997. doi:10.1007/BF02614317.
[53] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291–300. ACM, 2004. doi:10.1145/1007352.1007400.
[54] Martin G. Herold, Evangelos Kipouridis, and Joachim Spoerhase. Clustering to minimize cluster-aware norm objectives. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 255–287. SIAM, 2025. doi:10.1137/1.9781611978322.8.
[55] 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.
[56] 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.
[57] Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 731–740. ACM, 2002. doi:10.1145/509907.510012.
[58] 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), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 65:1–65:21, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2024.65.
[59] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Comput. Geom., 28(2-3):89–112, 2004. doi:10.1016/J.COMGEO.2004.03.003.
[60] Samir Khuller and Yoram J. Sussmann. The capacitated K-center problem. SIAM J. Discret. Math., 13(3):403–418, 2000. doi:10.1137/S0895480197329776.
[61] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J.ACM, 57(2):1–32, 2010. doi:10.1145/1667053.1667054.
[62] G. Laporte, S. Nickel, and F. S. da Gama. Location Science. Springer, 2015.
[63] Shi Li. Approximating capacitated k-median with (1 + $\varepsilon$ )k open facilities. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 786–796. SIAM, 2016. doi:10.1137/1.9781611974331.CH56.
[64] Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. ACM Trans. Algorithms, 13(2):22:1–22:18, 2017. doi:10.1145/2983633.
[65] Xiaofei Liu, Weidong Li, and Runtao Xie. A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem. Optimization Letters, 16(8):2373–2385, 2022. doi:10.1007/S11590-021-01831-Z.
[66] S. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28:129–137, March 1982. doi:10.1109/TIT.1982.1056489.
[67] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory (COLT’21), pages 3246–3264. PMLR, 2021. URL: http://proceedings.mlr.press/v134/makarychev21a.html.
[68] Jirı Matoušek. On approximate geometric $k$ -clustering. Discrete & Computational Geometry, 24(1):61–84, 2000. doi:10.1007/S004540010019.
[69] Nimrod Megiddo. On the complexity of some geometric problems in unbounded dimension. Journal of Symbolic Computation, 10(3):327–334, 1990. doi:10.1016/S0747-7171(08)80067-3.
[70] Clyde Monma and Subhash Suri. Partitioning points and graphs to minimize the maximum or the sum of diameters. In Graph Theory, Combinatorics and Applications (Proc. 6th Internat. Conf. Theory Appl. Graphs), volume 2, pages 899–912, 1989.
[71] S. Nickel and J. Puerto. Location Theory. Springer Science & Business Media, 2005.
[72] Ján Plesník. A heuristic for the $p$ -center problems in graphs. Discrete Applied Mathematics, 17(3):263–268, 1987. doi:10.1016/0166-218X(87)90029-1.
[73] Yicheng Xu, Yong Zhang, and Yifei Zou. A constant parameterized approximation for hard-capacitated k-means. CoRR, abs/1901.04628, 2019. arXiv:1901.04628.

[bib.bib1] [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 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1377–1399, 2023. doi:10.1109/FOCS57990.2023.00085.

[bib.bib2] [2] Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlodarczyk. Constant-factor FPT approximation for capacitated k-median. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 1:1–1:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ESA.2019.1.

[bib.bib3] [3] 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, July 11-15, 2016, Rome, Italy, 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.bib4] [4] Helmut Alt, Esther M Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P Fekete, Christian Knauer, Jonathan Lenchner, Joseph SB Mitchell, and Kim Whittlesey. Minimum-cost coverage of point sets by disks. In Proceedings of the twenty-second annual symposium on Computational geometry, pages 449–458, 2006.

[bib.bib5] [5] Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. Math. Program., 154(1-2):29–53, 2015. doi:10.1007/S10107-014-0857-Y.

[bib.bib6] [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):pages 79–101, 2010.

[bib.bib7] [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 J. Comput., 33(3):544–562, 2004. doi:10.1137/S0097539702416402.

[bib.bib8] [8] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The Hardness of Approximation of Euclidean k-Means. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry (SoCG 2015), volume 34 of Leibniz International Proceedings in Informatics (LIPIcs), pages 754–767, Dagstuhl, Germany, 2015. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SOCG.2015.754.

[bib.bib9] [9] Mihai Badŏiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In John H. Reif, editor, Proc. 34th Annual ACM Symposium on Theory of Computing (STOC’02), pages 250–257. ACM, 2002. doi:10.1145/509907.509947.

[bib.bib10] [10] Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, and Maryam Negahbani. Revisiting Priority k-Center: Fairness and Outliers. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.21.

[bib.bib11] [11] 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), volume 258 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:14, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2023.12.

[bib.bib12] [12] Sayan Bandyapadhyay and Kasturi R. Varadarajan. Approximate clustering via metric partitioning. In Seok-Hee Hong, editor, 27th International Symposium on Algorithms and Computation, ISAAC 2016, December 12-14, 2016, Sydney, Australia, volume 64 of LIPIcs, pages 15:1–15:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ISAAC.2016.15.

[bib.bib13] [13] Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav. Novel properties of hierarchical probabilistic partitions and their algorithmic applications. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1724–1767, 2024. doi:10.1109/FOCS61266.2024.00107.

[bib.bib14] [14] Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and diameters clustering. Algorithmica, 73(1):143–165, 2015. doi:10.1007/S00453-014-9907-3.

[bib.bib15] [15] Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained $k$ -means problem. Theory of Computing Systems, 62(1):93–115, 2018. doi:10.1007/S00224-017-9820-7.

[bib.bib16] [16] Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann. New approximability results for the robust $k$ -median problem. In Scandinavian Workshop on Algorithm Theory (SWAT’14), pages 50–61. Springer, 2014. doi:10.1007/978-3-319-08404-6_5.

[bib.bib17] [17] Santanu Bhowmick, Tanmay Inamdar, and Kasturi R. Varadarajan. Fault-tolerant covering problems in metric spaces. Algorithmica, 83(2):413–446, 2021. doi:10.1007/S00453-020-00762-Y.

[bib.bib18] [18] Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Geometric clustering to minimize the sum of cluster sizes. In Gerth Stølting Brodal and Stefano Leonardi, editors, Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, volume 3669 of Lecture Notes in Computer Science, pages 460–471. Springer, 2005. doi:10.1007/11561071_42.

[bib.bib19] [19] Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Geometric clustering to minimize the sum of cluster sizes. In Gerth Stølting Brodal and Stefano Leonardi, editors, Algorithms – ESA 2005, pages 460–471, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/11561071_42.

[bib.bib20] [20] Vladimir Braverman, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for ordered weighted clustering. In International Conference on Machine Learning (ICML’19), pages 744–753. PMLR, 2019. URL: http://proceedings.mlr.press/v97/braverman19a.html.

[bib.bib21] [21] Moritz Buchem, Katja Ettmayr, Hugo K. K. Rosado, and Andreas Wiese. A (3 + $\varepsilon$ )-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1738–1765. SIAM, 2024. doi:10.1137/1.9781611977912.69.

[bib.bib22] [22] Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitated k-median problems. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 722–736. SIAM, 2015. doi:10.1137/1.9781611973730.49.

[bib.bib23] [23] Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms, 13(2):23:1–23:31, 2017. doi:10.1145/2981561.

[bib.bib24] [24] Jaroslaw Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform capacitated k-median problem with 1+\epsilon capacity violation. In Quentin Louveaux and Martin Skutella, editors, Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, volume 9682 of Lecture Notes in Computer Science, pages 262–274. Springer, 2016. doi:10.1007/978-3-319-33461-5_22.

[bib.bib25] [25] Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase. Constant-factor approximation for ordered k median. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18), pages 620–631, 2018. doi:10.1145/3188745.3188930.

[bib.bib26] [26] Vasilis Capoyleas, Günter Rote, and Gerhard J. Woeginger. Geometric clusterings. J. Algorithms, 12(2):341–356, 1991. doi:10.1016/0196-6774(91)90007-L.

[bib.bib27] [27] Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 126–137, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3313276.3316322.

[bib.bib28] [28] Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. Journal of Computer and System Sciences, 68(2):417–441, 2004. Special Issue on STOC 2001. doi:10.1016/j.jcss.2003.07.014.

[bib.bib29] [29] Xianrun Chen, Dachuan Xu, Yicheng Xu, and Yong Zhang. Parameterized approximation algorithms for sum of radii clustering and variants. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors, Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada, pages 20666–20673. AAAI Press, 2024. doi:10.1609/AAAI.V38I18.30053.

[bib.bib30] [30] Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 952–958. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070569.

[bib.bib31] [31] Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm for k-median. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1556–1612. SIAM, 2022. doi:10.1137/1.9781611977073.65.

[bib.bib32] [32] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.

[bib.bib33] [33] Vincent Cohen-Addad and Karthik C. S. Inapproximability of clustering in lp metrics. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 519–539. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00040.

[bib.bib34] [34] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. Johnson coverage hypothesis: Inapproximability of $k$ -means and $k$ -median in ${\ell}_{p}$ -metrics. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1493–1530. SIAM, 2022. doi:10.1137/1.9781611977073.63.

[bib.bib35] [35] Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1–41:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.41.

[bib.bib36] [36] János Csirik, Leah Epstein, Csanád Imreh, and Asaf Levin. Online clustering with variable sized clusters. Algorithmica, 65(2):251–274, 2013. doi:10.1007/S00453-011-9586-2.

[bib.bib37] [37] Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 273–282. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.63.

[bib.bib38] [38] Sanjoy Dasgupta. The hardness of $k$ -means clustering. Technical Report CS2008-0916, University of California, San Diego, San Diego, CA, 2008.

[bib.bib39] [39] H. Gökalp Demirci and Shi Li. Constant approximation for capacitated k-median with (1+epsilon)-capacity violation. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 73:1–73:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.73.

[bib.bib40] [40] Srinivas Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor, and Peter Widmayer. Approximation algorithms for clustering to minimize the sum of diameters. Nordic J. of Computing, 7(3):185–203, September 2000.

[bib.bib41] [41] Henry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, and Stepan Zharkov. Inapproximability of maximum diameter clustering for few clusters. CoRR, abs/2312.02097, 2023. doi:10.48550/arXiv.2312.02097.

[bib.bib42] [42] Dimitris Fotakis and Paraschos Koutris. Online sum-radii clustering. Theor. Comput. Sci., 540:27–39, 2014. doi:10.1016/J.TCS.2013.03.010.

[bib.bib43] [43] 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), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1–56:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2022.56.

[bib.bib44] [44] Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair $k$ -means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 438–448, 2021. doi:10.1145/3442188.3445906.

[bib.bib45] [45] Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan. On metric clustering to minimize the sum of radii. Algorithmica, 57(3):484–498, July 2010. doi:10.1007/S00453-009-9282-7.

[bib.bib46] [46] 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.bib47] [47] 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.bib48] [48] Inge Li Gørtz and Anthony Wirth. Asymmetry in k-center variants. Theor. Comput. Sci., 361(2-3):188–199, 2006. doi:10.1016/J.TCS.2006.05.009.

[bib.bib49] [49] Kishen N. Gowda, Thomas W. Pensyl, Aravind Srinivasan, and Khoa Trinh. Improved bi-point rounding algorithms and a golden barrier for k-median. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 987–1011. SIAM, 2023. doi:10.1137/1.9781611977554.CH38.

[bib.bib50] [50] Dishant Goyal and Ragesh Jaiswal. Tight fpt approximation for constrained k-center and k-supplier. Theoretical Computer Science, 940:190–208, 2023. doi:10.1016/j.tcs.2022.11.001.

[bib.bib51] [51] Pierre Hansen and Brigitte Jaumard. Minimum sum of diameters clustering. Journal of Classification, 4(2):215–226, 1987.

[bib.bib52] [52] Pierre Hansen and Brigitte Jaumard. Cluster analysis and mathematical programming. Math. Program., 79:191–215, 1997. doi:10.1007/BF02614317.

[bib.bib53] [53] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291–300. ACM, 2004. doi:10.1145/1007352.1007400.

[bib.bib54] [54] Martin G. Herold, Evangelos Kipouridis, and Joachim Spoerhase. Clustering to minimize cluster-aware norm objectives. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 255–287. SIAM, 2025. doi:10.1137/1.9781611978322.8.

[bib.bib55] [55] 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.bib56] [56] 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.bib57] [57] Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 731–740. ACM, 2002. doi:10.1145/509907.510012.

[bib.bib58] [58] 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), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 65:1–65:21, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2024.65.

[bib.bib59] [59] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Comput. Geom., 28(2-3):89–112, 2004. doi:10.1016/J.COMGEO.2004.03.003.

[bib.bib60] [60] Samir Khuller and Yoram J. Sussmann. The capacitated K-center problem. SIAM J. Discret. Math., 13(3):403–418, 2000. doi:10.1137/S0895480197329776.

[bib.bib61] [61] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J.ACM, 57(2):1–32, 2010. doi:10.1145/1667053.1667054.

[bib.bib62] [62] G. Laporte, S. Nickel, and F. S. da Gama. Location Science. Springer, 2015.

[bib.bib63] [63] Shi Li. Approximating capacitated k-median with (1 + $\varepsilon$ )k open facilities. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 786–796. SIAM, 2016. doi:10.1137/1.9781611974331.CH56.

[bib.bib64] [64] Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. ACM Trans. Algorithms, 13(2):22:1–22:18, 2017. doi:10.1145/2983633.

[bib.bib65] [65] Xiaofei Liu, Weidong Li, and Runtao Xie. A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem. Optimization Letters, 16(8):2373–2385, 2022. doi:10.1007/S11590-021-01831-Z.

[bib.bib66] [66] S. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28:129–137, March 1982. doi:10.1109/TIT.1982.1056489.

[bib.bib67] [67] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory (COLT’21), pages 3246–3264. PMLR, 2021. URL: http://proceedings.mlr.press/v134/makarychev21a.html.

[bib.bib68] [68] Jirı Matoušek. On approximate geometric $k$ -clustering. Discrete & Computational Geometry, 24(1):61–84, 2000. doi:10.1007/S004540010019.

[bib.bib69] [69] Nimrod Megiddo. On the complexity of some geometric problems in unbounded dimension. Journal of Symbolic Computation, 10(3):327–334, 1990. doi:10.1016/S0747-7171(08)80067-3.

[bib.bib70] [70] Clyde Monma and Subhash Suri. Partitioning points and graphs to minimize the maximum or the sum of diameters. In Graph Theory, Combinatorics and Applications (Proc. 6th Internat. Conf. Theory Appl. Graphs), volume 2, pages 899–912, 1989.

[bib.bib71] [71] S. Nickel and J. Puerto. Location Theory. Springer Science & Business Media, 2005.

[bib.bib72] [72] Ján Plesník. A heuristic for the $p$ -center problems in graphs. Discrete Applied Mathematics, 17(3):263–268, 1987. doi:10.1016/0166-218X(87)90029-1.

[bib.bib73] [73] Yicheng Xu, Yong Zhang, and Yifei Zou. A constant parameterized approximation for hard-capacitated k-means. CoRR, abs/1901.04628, 2019. arXiv:1901.04628.

FPT Approximations for Capacitated Sum of Radii and Diameters

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Capacitated clustering

Theorem 1 (APX-hard).

Theorem 2 (No FPT-AS).

Theorem 3 (Main Theorem).

1.1 Other norm objectives

Theorem 4 (Uniform).

1.2 Sum of Diameters and cluster capacities

Capacitated Sum of Diameters

Theorem 5 (Uniform Diameters).

Theorem 6 (Non-Uniform Diameters).

Cluster capacities

2 Overview of techniques

▶ Remark 7 (Point assignment using matching and flows).

▶ Remark 8 (FPT and bounded guessing).

2.1 Non-uniform capacitated Sum of Radii

Invariant: do not touch the unprocessed.

Making progress: Good dense balls.

2.2 Uniform capacities

Improvement for ℓ𝒑 norm objectives

2.3 Hardness of FPT-approximation for uniform capacities

3 Further related work

References

$\blacktriangleright$ Remark 7 (Point assignment using matching and flows).

$\blacktriangleright$ Remark 8 (FPT and bounded guessing).

Improvement for $\ell_{p}$ norm objectives