Clustering in Varying Metrics

Chakrabarty, Deeparnab; Conroy, Jonathan; Sarkar, Ankita

doi:10.4230/LIPIcs.FSTTCS.2025.19

Clustering in Varying Metrics

Deeparnab Chakrabarty Department of Computer Science, Dartmouth College, Hanover, NH, USA Jonathan Conroy

Department of Computer Science, Dartmouth College, Hanover, NH, USA Ankita Sarkar

Department of Computer Science, Dartmouth College, Hanover, NH, USA

Abstract

We introduce the aggregated clustering problem, where one is given $T$ instances of a center-based clustering task over the same $n$ points, but under different metrics. The goal is to open $k$ centers to minimize an aggregate of the clustering costs – e.g., the average or maximum – where the cost is measured via $k$ -center/median/means objectives. More generally, we minimize a norm $\Psi$ over the $T$ cost values. We show that for $T\geq 3$ , the problem is inapproximable to any finite factor in polynomial time. For $T=2$ , we give constant-factor approximations. We also show W[2]-hardness when parameterized by $k$ , but obtain $f(k,T)\mathrm{poly}(n)$ -time 3-approximations when parameterized by both $k$ and $T$ .

When the metrics have structure, we obtain efficient parameterized approximation schemes (EPAS). If all $T$ metrics have bounded $\varepsilon$ -scatter dimension, we achieve a $(1+\varepsilon)$ -approximation in $f(k,T,\varepsilon)\mathrm{poly}(n)$ time. If the metrics are induced by edge weights on a common graph $G$ of bounded treewidth $\mathsf{tw}$ , and $\Psi$ is the sum function, we get an EPAS in $f(T,\varepsilon,\mathsf{tw})\mathrm{poly}(n,k)$ time. Conversely, unless (randomized) ETH is false, any finite factor approximation is impossible if parametrized by only $T$ , even when the treewidth is $\mathsf{tw}=\Omega(\mathrm{poly}\log n)$ .

Keywords and phrases:

Clustering, approximation algorithms, LP rounding, parameterized and exact algorithms, dynamic programming, fixed parameter tractability, hardness of approximation

Funding:

Deeparnab Chakrabarty: Work partially funded by NSF grants CCF-2041920 and CCF-2402571.

Jonathan Conroy: Work partially funded by the U.S. National Science Foundation CAREER Award under the Grant No. CCF-2443017.

Ankita Sarkar: Work partially funded by NSF grants CCF-2041920 and CCF-2402571.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Facility location and clustering ; Theory of computation

\rightarrow

Fixed parameter tractability

Editors:

C. Aiswarya, Ruta Mehta, and Subhajit Roy

Series and Publisher:

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

1 Introduction

Clustering problems such as the $k$ -supplier or the $k$ -median problem are classic discrete optimization problems which have formed the bedrock of many problems in operations research. In its simplest form, the objective is to “open” $k$ locations in a metric space such that some function (eg, max or sum) of the distances of clients to the nearest open facility is minimized. Such problems have been extensively studied over the past 50 years [39, 53, 24, 41, 23, 7, 25, 14, 49, 57, 19, 43, 18, 50, 52, 20, 26, 33, 4, 17], and we have a very good understanding on the approximability of many of these problems.

In this paper, we consider clustering problems when the distance function underlying the metric space can change over time. To give a toy example, imagine that the clients are households in a New England town, and the distances are travel times over the road network in the town. On one hand, travel times may be quite different in January and June given the weather differences over the months. On the other hand, one can’t hope to open different locations in different seasons. Our decision ought to take into account the different costs over time, for example by selecting a set of facilities that minimizes the average cost over the year. Although this sounds a natural question, to our knowledge what happens to the complexity of clustering with changing metrics hasn’t been studied so far.¹¹1One may be tempted to simply perform clustering on a single metric space defined by average distances over all months. However, this does not work: the cost of a client at each timestep is computed by take a minimum over a set of facilities, and this minimum is not preserved when we take an average. Formally, we study the following problem.

Definition 1 (Aggregate Clustering Problems).

We are given $V=F\cup C$ , a finite set of $n$ points where $C$ is the set of clients and $F$ is a set of facilities²²2 $F$ and $C$ need not be disjoint, and one can imagine the case of $F=C$ as a special but instructive case.. We are given $T$ distance functions $d_{t}(\cdot,\cdot)$ over $V\times V$ which are symmetric and satisfy triangle-inequality. We are given a parameter $k\in\mathbb{Z}$ . Finally, we are given an aggregator function $\Psi:\mathbb{R}^{T}_{\geq 0}\to\mathbb{R}_{\geq 0}$ . The goal is to “open” a subset $S\subseteq F$ of $k$ facilities that minimize a certain objective function (depending on the problem variant). The objective functions are:

$\blacksquare$

$\Psi\left(\mathrm{cost}_{\infty}(d_{t};S):t\in[T]\right)$ , where $\mathrm{cost}_{\infty}(d_{t};S):=\max_{j\in C}d_{t}(j,S)$ , in the $\Psi$ -aggregate $k$ -supplier problem.³³3We use the notation $d_{t}(j,S)$ to mean $\min_{i\in S}d_{t}(j,i)$ .
$\blacksquare$

$\Psi\left(\mathrm{cost}_{1}(d_{t};S):t\in[T]\right)$ , where $\mathrm{cost}_{1}(d_{t};S):=\sum_{j\in C}d_{t}(j,S)$ , in the $\Psi$ -aggregate $k$ -median problem.
$\blacksquare$

$\Psi\left(\mathrm{cost}_{z}(d_{t};S):t\in[T]\right)$ , where $\mathrm{cost}_{z}(d_{t};S):=\left(\sum_{j\in C}d_{t}(j,S)^{z}\right)^{1/z}$ , in the $\Psi$ -aggregate $(k,z)$ -clustering problem.

When it is clear from context, we denote the objective function as $\mathrm{aggcost}(\cdot)$ .

The above problem also can be thought of as a stochastic/robust version of clustering under uncertainty where the uncertainty is over the distances. Note that when $\Psi$ is the sum-function, we wish to find a solution which minimizes the average $k$ -supplier/ $k$ -median cost of the returned solution $S$ , where the average is over the $T$ “scenarios” (we are assuming the full-information setting); when $\Psi$ is the max-function, we get the robust optimization setting. In the literature [5, 52, 26], stochastic/robust clustering has been studied when the metric is fixed but the uncertainty is over the client sets. We can consider a generalized version of aggregate clustering, which models client demands changing over time.

Definition 2 (Generalized Aggregate Clustering).

Apart from the $t$ distances, we have $t$ weight functions $w_{t}:C\to\mathbb{R}$ . In the objective functions, we modify $\mathrm{cost}$ s by multiplying $d_{t}(j,S)$ ’s with $w_{t}(j)$ . More precisely, $\mathrm{cost}_{z}(d_{t},S)=\left(\sum_{j\in C}w_{t}(j)\cdot d_{t}(j,S)^{z}% \right)^{1/z}$ and $\mathrm{cost}_{\infty}(d_{t};S)=\max_{j\in C}w_{t}(j)d_{t}(j,S)$ . In particular, if $w_{t}:C\to\{0,1\}$ , then this models having different client sets at different times.

All our upper bounds apply for generalized aggregate clustering, and all our lower bounds hold even for the vanilla version of aggregate clustering. In fact, in Observation 27 we present a weak equivalence between the two problems, by showing that any algorithm for vanilla aggregate clustering can solve generalized aggregate clustering with $\left\{0,1\right\}$ weights, i.e. aggregate clustering where the client set is allowed to change over time.

1.1 Our Findings

General Metrics.

In its full generality, unfortunately, the aggregrate clustering problem becomes very hard when the number of scenarios $T$ becomes $3$ or larger. In Theorem 3 we show that it is NP-hard to distinguish between zero and non-zero solutions when $T\geq 3$ . To complement this result, we show (in Theorems 7 and 16) that when $T=2$ , both the (generalized) $\Psi$ -aggregate $k$ -median and $k$ -supplier problems have polynomial time $O(1)$ -approximations when $\Psi$ is any norm. In fact, for $k$ -supplier, we match the optimal $3$ -approximation that is known at $T=1$ [39, 53]. Both the above results, at a very high level, follow from the fact that bipartite matching (or rather, partition matroid intersection) is tractable, while 3D-matching is NP-hard.

Given the above hardness for $T\geq 3$ , we attempt to bypass it in two ways: (i) investigating fixed-parameter tractable approximation algorithms, and (ii) imposing additional structure over the metrics in various scenarios.

Constant-factor FPT approximation algorithms.

The hardness for $T=3$ clearly shows one can’t expect $f(T)\cdot\mathrm{poly}(n,k)$ -time approximation algorithms. Moreover, we show (in Theorem 5) that it is also hard to obtain $f(k)\cdot\mathrm{poly}(n,T)$ -time approximation algorithms: we encode the $k$ -hitting set problem as an instance of aggregate clustering, and our lower bound follows from the $W[2]$ hardness of $k$ -hitting set [32, Theorem 13.12]. On the other hand, if we allow $k$ and $T$ to be both fixed parameters, then (in Theorem 19) we obtain an $f(k,T)\cdot\mathrm{poly}(n)$ -time $(3+\varepsilon)$ -approximation. The high level idea for this is as follows: Suppose we have $T$ partitions of a universe $U$ , and we must decide if there is a $k$ -sized subset that is a simultaneous hitting set for all $T$ partitions. In $(k+1)^{kT}\cdot\mathrm{poly}(n)$ -time, we can guess for each $t\in[T]$ and $i\in[k]$ the part in the $t$ ^th partition that the $i$ ^th hitting element hits. Such an idea is the core of many FPT approximation algorithms for clustering [1, 12, 38].

Approximation schemes in structured metrics.

To impose structure on the metric, we note that any finite metric $d_{t}$ is a shortest path metric on an undirected base graph $G=(V,E)$ with weights $w_{t}(e)$ on the edges. Note that our restriction of having the same graph $G$ across scenarios is without loss of generality if we allow a complete graph. Furthermore, in many applications, such as the road-network application mentioned in the early paragraphs of the introduction, this indeed is the case where the “weights” change over the seasons but the underlying network remains the same. Can one obtain better algorithmic results exploiting the structure of the underlying undirected base graph $G$ ?

Unfortunately, our hardness results apply even for very simple base graphs $G$ . In particular, our reduction from hitting set (Theorem 5, which rules out any finite factor approximation algorithms in $f(k)\cdot\mathrm{poly}(n,T)$ time) can be carried out even when $G$ is a star. Moreover, our reduction from 3D matching (Theorem 3, which rules out any $f(T)\cdot\mathrm{poly}(n,k)$ -time finite factor approximations) can be carried out even when $G$ is a grid graph (see Theorem 4).

Nevertheless, we bypass this hardness by designing $1+\varepsilon$ approximation algorithms in time $f(\varepsilon,k,T)\cdot\mathrm{poly}(n)$ (ie, EPASes in parameters $k$ and $T$ ) for a broad class of structured input metrics, which includes (for example) the case when $G$ is a planar graph. More precisely, we design approximation algorithms whenever input metric $d_{t}$ has bounded scatter dimension. This concept was recently introduced by Abbasi et al. [1], along with an algorithm demonstrating that metrics of bounded scatter dimension admit $f(\varepsilon,k)\cdot\mathrm{poly}(n)$ time $1+\varepsilon$ -approximation algorithms for many clustering problems. We generalize their ideas to obtain an EPAS for the (generalized) aggregate $(k,z)$ -clustering problem. Bounded scatter dimension captures a rich class of metrics, including doubling metrics, shortest-path metrics on planar or minor-free graphs [13], and metrics of bounded highway dimension⁴⁴4We are not aware of a published proof that highway dimension has bounded scatter dimension, but the claim can be found at timestamp 0:52 in the recorded FOCS 2023 talk on [1] (see link https://focs.computer.org/2023/schedule/) and also in [12]. – this last class, which was introduced to model transportation networks [3, 2], may be of particular interest in light of our road-network application from earlier. We emphasize that our lower bounds on the star and grid apply to metrics of bounded scatter dimension, so our FPT $(k,T)$ approximation is essentially the best one could hope to achieve (up to the $1+\varepsilon$ approximation) in this setting.

Additionally, we consider the case when $G$ is a tree, or more generally a bounded-treewidth graph. As bounded-treewidth graphs have bounded scatter dimension, our $f(\varepsilon,k,T)\cdot\mathrm{poly}(n)$ -time algorithm from above applies. However, we can do even better – we obtain a $(1+\varepsilon)$ -approximation for the sum-aggregate $(k,z)$ -clustering problem in time $f(T,\varepsilon)\cdot\mathrm{poly}(n,k)$ , by generalizing a folklore dynamic programming algorithm for $k$ -median on bounded-treewidth graphs [6, 42, 29]. Parameterizing by $T$ is necessary, because of our hardness result on the star. On the other hand, we can avoid parameterizing by $k$ because our hardness for the $T=3$ case only applies $G$ is a grid graph, which has high treewidth – recall that graphs of bounded treewidth are precisely those graphs which exclude a grid as a minor [54, 28]. In fact, we show in Theorem 4 that our $T=3$ hardness rules out $f(T)\cdot\mathrm{poly}(n)$ -time algorithms for any graph $G$ that has sufficiently large treewidth (specifically, $\Omega(\log^{295}n)$ ), whereas our upper bound in Theorem 24 achieves $f(T)\cdot\mathrm{poly}(n)$ runtime so long as $G$ has treewidth $o(\log n/\log\log n)$ (see Remark 25). Thus, our upper and lower bounds show that the treewidth of the base graph $G$ almost entirely captures the tractability of FPT( $T$ ) algorithms for the sum-aggregate⁵⁵5We expect that a DP could be designed for other $\Psi$ -aggregator norms, but in this extended abstract we only consider $\Psi=$ sum. clustering problem (up to some $1+\varepsilon$ approximation factor, and up to some $\mathrm{poly}(\log n)$ gap in the treewidth between our upper and lower bounds).

Open Directions

We end this section mentioning some open directions for future study. If one observes the metrics we use to prove our hardness results, we notice that they “change a lot” as one moves from $d_{t}$ to $d_{t+1}$ . Can one obtain positive algorithmic results if this change is bounded? Concretely, assume $d_{t}$ is the shortest path metric on $G_{t}=(V,E_{t})$ and $d_{t+1}$ is the same on $G_{t+1}=(V,E_{t+1})$ . What if we forced $|E_{t}\Delta E_{t+1}|\leq O(1)$ ? Again taking the road-network example, these could lead to certain road-closures or road-building, but in a single period perhaps not too many edges are added or deleted. We do not know any lower bound for this version, nor do we know how to design algorithms. Structurally, this seems to require an understanding of how shortest paths change with insertion/deletion of edges which may be of independent interest.

Another interesting, but slightly less concrete, direction is to explore online algorithms where an algorithm is allowed to change the centers but the distance metric is revealed only after the algorithms decision is made. Can one design “low-regret” algorithms as in [59]? The sum-aggregate objective is in fact the benchmark with which regret is measured, and our results show that approximating this benchmark for general metrics is hard. With this in view, what would be a good definition of regret?

Coming back to aggregate clustering, a concrete open problem is the following. The aforementioned hardness when $G$ is a star actually has $F\neq C$ , but the case of $V=C=F$ is also interesting. Are there $f(T)\cdot\mathrm{poly}(n,k)$ approximation or even exact algorithms for $\Psi$ -aggregated $k$ -supplier/median problem when $G$ is a tree? We believe this is an interesting generalization of $k$ -median problem on trees and worthy of exploration.

1.2 Related Works

As noted earlier, approximation algorithms for clustering problems have a rich history and we don’t attempt to summarize this. Rather we mention the works most related to the “changing metric” viewpoint.

Deng, Li, and Rabani [33] consider the $k$ -clustering problems in a dynamic setting in which both clients and facilities may change over time (though the metric remains the same). The algorithm is allowed to change the open facilities over time, and the objective is to minimize the clustering costs and the distances that open facilities move over time. Their main results, at a high level, are in lockstep with our first set of results for aggregate clustering (on the tractability of $T=2$ vs $T\geq 3$ scenarios); though our findings and theirs do not imply one another. Their setting has an ambient metric space $(X,d)$ and, over $T$ timesteps, there are client and facility sets $C_{t},F_{t}\subseteq X$ for each timestep $t$ . The goal is to pick $k$ -sized solutions $S_{t}\subseteq F_{t}$ at each time step minimizing a certain objective function.

As mentioned earlier, our problem is related to stachastic/robust clustering problems which consider scenarios where client sets change but the algorithm needs to open the same set of $k$ centers to serve these. This question was studied by Anthony, Goyal, Gupta, and Nagarajan [5] who obtain a $O(\log T+\log n)$ -approximation for the robust $k$ -median problem discussed earlier. They also show that stochastic $k$ -center (i.e. stochastic $k$ -supplier with $F=C$ ) is as hard to approximate as the densest- $k$ -subgraph problem. Makarychev and Vakilian [52] obtain an $\left(e^{O(z)}\frac{\log T}{\log\log T}\right)$ -approximation to robust $(k,z)$ -clustering. Along with Chlamtáč, the same authors [26] subsequently generalize this approximation algorithm to clustering with cascaded norm objectives, i.e. objectives of the form $\Big(\sum_{t=1}^{T}\big(\sum_{j\in C_{t}}d(j,S)^{z}\big)^{q/z}\Big)^{1/q}$ . When $z\geq q$ , they obtain a near-optimal $O\left(k^{O_{z,q}(1)}\right)$ -approximation. When $z\leq q<\infty$ , they obtain an $O_{z,q}(1)$ -approximation.

Another related line of work is dynamic algorithms for clustering where clients come and go, and the algorithm needs to update the solution fast and maintain $O(1)$ -approximations. There has been a lot of work [47, 22, 31, 36, 8, 10, 46, 37, 11, 9] recently on these probelms. We point the readers to [11] (and references within) for dynamic $k$ -center, and [9] (and references within) for dynamic $k$ -median. It is curious to see if techniques from these can address the questions mentioned in the open-directions paragraph earlier.

2 Hardness of Approximation

Theorem 3 (Hardness of approximation when $T\geq 3$ ).

For any homogeneous aggregator $\Psi$ and any $z\in\mathbb{N}\cup\left\{\infty\right\}$ , there is no $f(T)\mathrm{poly}(n,k)$ -time finite-factor approximation for $\Psi$ -aggregate $(k,z)$ -clustering on finite metrics on $n$ -vertices unless $P=NP$ . The result holds even for $T=3$ .

Proof.

We show that it is NP-hard to decide whether the optimum value is finite or infinite for any $\Psi$ -aggregate $(k,z)$ -clustering problem. We reduce from the (perfect) 3D Matching problem where, recall, we are given a $3$ -partite hypergraph $H=(V_{1}\uplus V_{2}\uplus V_{3},E)$ where $|V_{1}|=|V_{2}|=|V_{3}|$ any every hyperedge $e\in E$ intersects every $V_{t}$ exactly once. The goal is to decide whether or not there exists a matching (pairwise disjoint subset) $M\subseteq E$ of hyperedges which spans all vertices. Equivalently, $|M\cap e|=1$ for all $e\in E$ . Given such a 3D Matching instance $(V_{1}\uplus V_{2}\uplus V_{3},E)$ , we construct an aggregate clustering instance on $T=3$ metrics, where the underlying graph is a complete graph $G$ with vertex set $E$ . The client set $C=F=E$ and $k\coloneqq\left\lvert V_{1}\right\rvert=\left\lvert V_{2}\right\rvert=\left% \lvert V_{3}\right\rvert$ . For each metric $t\in\left\{1,2,3\right\}$ and each two distinct clients $e,e^{\prime}$ , we set the distance $d_{t}(e,e^{\prime})\coloneqq 0$ if $e\cap e^{\prime}\cap V_{t}\neq\emptyset$ , i.e. if they agree on their vertex in $V_{t}$ . Otherwise set $d_{t}(e,e^{\prime})\coloneqq\infty$ . It is easy to see that each $d_{t}$ is in fact a metric since if $e_{1},e_{2}$ share the same $V_{t}$ endpoint as do $e_{2},e_{3}$ , then they must be the same endpoint and thus $e_{1},e_{3}$ share that as well. It remains to show that the clustering instance admits $0$ -cost solutions iff the original instance admits a perfect 3D matching.

$\blacksquare$

Suppose this clustering instance admits a $0$ -cost solution. Call this solution $S$ . Fix a $t\in\left\{1,2,3\right\}$ and $v\in V_{t}$ . Let $E(v)$ be the set of hyperedges that contain $v$ . We know by construction that, $\forall e\in E(v),d_{t}(e,S)=0$ , i.e. $\exists e^{\prime}\in S$ such that $e,e^{\prime}$ agree on their vertex in $V_{t}$ . But then this vertex must be $v$ itself. Thus $e^{\prime}\in E(v)\cap S$ , so $\left\lvert E(v)\cap S\right\rvert\geq 1$ .

Since $\left\lvert V_{t}\right\rvert=\left\lvert S\right\rvert$ , this means that for each $v\in V_{t}$ , $\left\lvert E(v)\cap S\right\rvert=1$ . So $S$ is a perfect 3D matching.
$\blacksquare$

Suppose $M$ is a perfect 3D matching in the original instance. Fix $t\in\left\{1,2,3\right\}$ and $e\in C$ such that $e\cap V_{t}=\left\{v\right\}$ . We know that $M\cap E(v)\neq\emptyset$ , so fix $e^{\prime}\in M\cap E(v)$ . Then $e\cap e^{\prime}\cap V_{t}=\left\{v\right\}$ , i.e. $d_{t}(e,e^{\prime})=0$ , and so $d_{t}(e,M)=0$ . So for each $t\in\left\{1,2,3\right\}$ and each $e\in C$ , we have $d_{t}(e,M)=0$ . Thus $\mathrm{aggcost}(M)=0$ .

$\hfill\blacktriangleleft$

Using techniques from graph drawing literature, one can show that our reduction Theorem 3 holds even when the base graph is a grid graph. Furthermore, we can rule out $\mathrm{poly}(n)$ -time algorithms for aggregate clustering whenever the base graph $G$ contains even a relatively small ( $\tilde{\Omega}(\log^{3}n)\times\tilde{\Omega}(\log^{3}n)$ ) grid minor, and consequently has relatively small treewidth; this follows from the fact that, under the randomized exponential time hypothesis, it is hard to obtain a $2^{o(n)}$ -time algorithm for 3D matching [45, 44]. We defer the details to the full version [16].

Theorem 4.

Let $G$ be any $n$ -vertex graph with treewidth $\mathsf{tw}=\Omega(\log^{295}n)$ . (For example, one may simply take $G$ to be a $\sqrt{n}\times\sqrt{n}$ grid graph.) For any homogenous aggregator $\Psi$ and any $z\in\mathbb{N}\cup\left\{\infty\right\}$ , there is no $f(T)\mathrm{poly}(n,k)$ -time finite-factor approximation for $\Psi$ -aggregate $(k,z)$ -clustering problem when the base graph inducing the metrics is $G$ , unless the randomized exponential time hypothesis is false. This results holds even for $T=3$ .

Next, we give a different reduction to rule out that FPT algorithms parameterized by $k$ , even when the base graph is a star.

Theorem 5 (Hardness of approximation on stars in FPT time.).

For any homogenous aggregator $\Psi$ and any $z\in\mathbb{N}\cup\left\{\infty\right\}$ , there is no $f(k)\mathrm{poly}(n,T)$ -time finite-factor approximation algorithms for the $\Psi$ -aggregate $(k,z)$ -clustering problem even when the base graph $G$ inducing the metrics is a star, unless W[2] = FPT.

Proof.

We reduce from $k$ -hitting set, which is W[2] hard when parameterized by $k$ [32]. Suppose we are given an instance of $k$ -hitting set defined by a universe $U=\left\{v_{1},\ldots,v_{n}\right\}$ of $n$ points, a set $\mathcal{X}=\left\{X_{1},\ldots,X_{m}\right\}$ of $m$ subsets of $U$ , and an integer $k$ ; our task is to determine whether there are $k$ points in $U$ that hit all sets of $\mathcal{X}$ . We construct an instance of aggregate clustering as follows. Let $G$ be a star graph with a root vertex $r$ connected to $n$ leaves $v_{1},\ldots,v_{n}$ . Let the facility set be $F\coloneqq\left\{v_{1},\ldots,v_{n}\right\}$ , and let the client set (in every metric) be $C=\left\{r\right\}$ . We define $T\coloneqq m$ distances functions, one for each set $X_{t}\in\mathcal{X}$ , as follows: in the $t$ -th metric, we set the weight of edge $(r,v_{i})$ to be 0 if $v_{i}\in X_{t}$ and $\infty$ otherwise.

It remains to show that the $\Psi$ -aggregate $(k,z)$ -clustering problem has finite cost iff there is a hitting set of size $k$ .

$\blacksquare$

First we show that, if there is a hitting set $S$ of size $k$ , then the $\mathrm{aggcost}(S)=0$ . Indeed, for every $t\in[T]$ , there exists some $v_{i}\in S$ with $v_{i}\in X_{t}$ and so $d_{t}(r,S)\leq d_{t}(r,v_{i})=0$ . In particular, the $(k,z)$ -clustering cost paid by the client set $C=\left\{r\right\}$ in each metric is $0$ , and so the $\Psi$ -aggregate cost is also 0 because $\Psi$ is a norm.
$\blacksquare$

Similarly, if there is a set $S$ of $k$ facilities such that $\mathrm{aggcost}(S)<\infty$ , then we claim $S$ is a hitting set. Indeed, consider some $X_{t}\in\mathcal{X}$ . Since $S$ has finite cost, we know that $d_{t}(r,S)<\infty$ and in particular there exists some $v_{i}\in S$ with $d_{t}(r,v_{i})=0$ . By construction, $v_{i}$ hits $X_{t}$ .

$\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 6.

The above reduction additionally shows that designing bicriteria approximation algorithms for aggregate clustering remains hard, due to the hardness of approximation of hitting set [34] – there exists some $\beta=O(\log n)$ such that it is NP-hard to distinguish between the case that there is a hitting set of size $k$ and the case that there is no hitting set of size $\beta k$ .

3 Constant-factor approximations for $T=2$ scenarios

In this section we extend the vanilla $O(1)$ -approximations for $k$ -supplier and $k$ -median for the case of $T=2$ scenarios; this contrasts with the inapproximability for $T\geq 3$ (Theorem 3). For simplicity, we restrict our exposition when the aggregator function $\Psi$ is just the sum, but we later point out in Remark 17 why it holds for any homogeneous aggregator such as a norm. In Remark 18 we explain how our algorithms generalize for $(k,z)$ -clustering.

At a high level, both the extensions from vanilla work because (a very simple) matroid intersection is polynomial time tractable, while even 3D-matching is NP-hard; the latter was the root of the hardness for $T\geq 3$ aggregate clustering. We begin with the $k$ -supplier problem which explains the previous line, and then show how ideas from the “matroid-median” problems solves the aggregate $k$ -median problem for $T=2$ .

3.1 $3$ -approximation for Aggregate $𝒌$ -Supplier

Let $\mathtt{OPT}$ be the optimal set of $k$ -suppliers which minimizes $\mathrm{cost}_{\infty}(d_{1};\mathtt{OPT})+\mathrm{cost}_{\infty}(d_{2};% \mathtt{OPT})$ , where recall $\mathrm{cost}_{\infty}(d_{t};\mathtt{OPT})=\max_{j\in C}d_{t}(j,\mathtt{OPT})$ . Let us denote $\mathrm{cost}_{\infty}(d_{t};\mathtt{OPT})$ as $\mathtt{opt}_{t}$ for $t\in\{1,2\}$ . Note that this can be guessed in $\mathrm{poly}(n)$ -time (one could make this poly-logarithmic in $n$ using “binary search” techniques) and so we assume we know $\mathtt{opt}_{1}$ and $\mathtt{opt}_{2}$ . We now describe an algorithm, very similar to the one in [39], which returns a subset $\mathtt{ALG}$ of facilities with $\mathrm{cost}_{\infty}(d_{t};\mathtt{ALG})\leq 3\mathtt{opt}_{t}$ for $t\in\{1,2\}$ . This implies a $3$ -approximation for the aggregate $k$ -supplier problem for the $T=2$ case for any homogeneous aggregator $\Psi$ .

For $t\in\{1,2\}$ , define $B_{t}(a,r)=\left\{b\in F\cup C:d_{t}(a,b)\leq r\right\}$ . We run the Hochbaum-Shmoys [39] filtering algorithm on each metric $d_{t}$ with parameter $\mathtt{opt}_{t}$ . To briefly describe this: (i) initially all clients are “uncovered”, (ii) pick an arbitrary uncovered client $j\in C$ and add it to a set $R_{t}$ of representatives, define $B_{t}(j,2\mathtt{opt}_{t})\cap C$ to be $j$ ’s “children”, and mark $j$ and all its children as “covered”, and (iii) continue the above till all clients covered. The main observations, which are easy to check using triangle inequality and the fact that $\mathtt{opt}_{t}$ ’s were correct guesses, are the following for $t\in\{1,2\}$ :

$\blacksquare$

The collection of balls $\left\{B_{t}(j,\mathtt{opt}_{t})\cap F\right\}_{j\in R_{t}}$ are pairwise disjoint.
$\blacksquare$

For any $j\in R_{t}$ , $B_{t}(j,\mathtt{opt}_{t})\cap\mathtt{OPT}\neq\emptyset$ . The above two imply $|R_{t}|\leq k$ .
$\blacksquare$

For every $v\in C$ , $d_{t}(v,R_{t})\leq 2\mathtt{opt}_{t}$ .

We now construct a solution $\mathtt{ALG}$ of size $\leq k$ such that for any $t\in\{1,2\}$ and any $j\in R_{t}$ , we have $\mathtt{ALG}\cap B_{t}(j,\mathtt{opt}_{t})\neq\emptyset$ ; that is, $\mathtt{ALG}$ hits every ball in the above two collections. This can be solved using matroid intersection since there are only two collections of disjoint balls. Once we have such an $\mathtt{ALG}$ , it is easy to see using triangle inequality that, for any $t\in\{1,2\}$ , $d_{t}(v,\mathtt{ALG})\leq d_{t}(v,j)+d_{t}(j,\mathtt{ALG})\leq 3\mathtt{opt}_{t}$ where $j$ was $v$ ’s representative in $R_{t}$ .

To give more details on how to find $\mathtt{ALG}$ , for $t\in\{1,2\}$ define the partition $\mathcal{P}_{t}$ of $F$ formed by $\left\{B_{t}(j,\mathtt{opt}_{t})\cap F\right\}_{j\in R_{t}}\cup Z_{t}$ , where $Z_{t}$ are all the facilities of $F$ not in any ball. We define the “budget” of each part to be $|\left\{B_{t}(j,\mathtt{opt}_{t})\cap F\right\}|-1$ – this is the number of facilities $\mathtt{ALG}$ can “leave out” – and set the budget of $Z_{t}$ to be $|Z_{t}|$ . We say $S\subseteq F$ is independent in partition matroid $t$ if it picks at most budget from each part; we seek the set $S\subseteq F$ of the largest cardinality which is independent in both partition matroids. We return $\mathtt{ALG}:=F\setminus S$ . By design, $\mathtt{ALG}$ hits every $B_{t}(j,\mathtt{opt}_{t})$ for $t\in\{1,2\}$ and $j\in R_{t}$ . Since $F\setminus\mathtt{OPT}$ is a candidate $S$ which is in the intersection of the two partition matroids, we get $|\mathtt{ALG}|=|F|-|S|\leq|F|-|F\setminus\mathtt{OPT}|=|\mathtt{OPT}|\leq k$ .

In sum, we can find a solution $\mathtt{ALG}$ such that $\mathrm{cost}_{\infty}(d_{t};\mathtt{ALG})\leq 3\mathtt{opt}_{t}$ for $t\in\{1,2\}$ , and thus $\Psi(\mathrm{cost}_{\infty}(d_{1};\mathtt{ALG}),\mathrm{cost}_{\infty}(d_{2};% \mathtt{ALG}))\leq 3\Psi(\mathtt{opt}_{1},\mathtt{opt}_{2})$ . This completes the proof of the following theorem.

Theorem 7.

When $T=2$ , there is a $\mathrm{poly}(n)$ -time $3$ -approximation algorithm for $\Psi$ -aggregate $k$ -supplier on $n$ vertices for any homogeneous aggregator $\Psi$ .

3.2 $O(1)$ -approximation for Aggregate $𝒌$ -Median

To obtain an constant approximation for the $k$ -median problem one has to work a bit harder, but the underlying idea behind tractability is still the tractability of matroid intersection. More precisely, it is the integrality of a polytope defined by two laminar set systems. At a high level, such an issue arises when one studies the matroid median problem where there is only one metric but one has the extra constraint that the set of facilities opened must be an independent set of a certain matroid. One solves this problem by rounding a solution to an LP-relaxation where matroid intersection (or rather the integrality fact mentioned above) forms a core component with the given matroid being one matroid, and the other formed via “filtering” technique a la [55, 23]. In our case the situation is similar at such a high-level – the two “matroids” are formed by the filtering ideas for the $T=2$ scenarios – but the details do need working out, and we show this below. We use the framework set by Swamy [57] for the matroid-median problem, but other frameworks (such as the iterated rounding framework of [43]) could possibly lead to better approximation factors; in this work, we didn’t optimize the latter.

Linear Programming Relaxation

We begin by writing a linear programming relaxation for our problem. Recall that, in the standard linear programs for $k$ -median, matroid median, etc. [23, 48, 57, 33], variables of the form $x(i,v)$ denote whether or not the client $v$ uses the facility $i$ , so that $v$ ’s share of the cost is $\sum_{i\in F}d(v,i)x(i,v)$ . In an integral solution $S\subseteq F$ , each $v$ has a unique $i_{v}\in S$ such that $x(i_{v},v)=1$ , and $d(i_{v},v)=d(v,S)$ .

In our problem, we need two sets of such $x$ -variables, because given an integral solution $S\subseteq F$ , a client $v$ can use different facilities under different metrics; that is, there can be distinct $i_{1},i_{2}\in S$ s.t. $d_{1}(v,S)=d_{1}(v,i_{1})$ and $d_{2}(v,S)=d_{2}(v,i_{2})$ . So for each $t\in\left\{1,2\right\}$ , we define variables $\left\{x_{t}(i,v)\right\}_{v\in C,i\in F}$ denoting whether or not the client $v$ uses the facility $i$ under the metric $d_{t}$ . We also have variables $\left\{y(i)\right\}_{i\in F}$ which, like in the standard $k$ -median LP [23, 25], denote whether or not the facility $i$ is picked into our solution. This allows us to write linear constraints similar to the standard LP for $k$ -median. We use ${\sf lp}$ to refer to the fractional optimum of the linear program relaxation.

minimize:	$\displaystyle\sum_{v\in C}\sum_{i\in F}d_{1}(i,v)x_{1}(i,v)+\sum_{v\in C}\sum_% {i\in F}d_{2}(i,v)x_{2}(i,v)$		(LP)
	$\displaystyle\sum_{i\in F}y(i)\leq k$		(LP1)
	$\displaystyle x_{t}(i,v)\leq y(i)$	$\displaystyle\forall t\in\left\{1,2\right\},v\in C,i\in F$	(LP2)
	$\displaystyle\sum_{i\in F}x_{t}(i,v)=1$	$\displaystyle\forall t\in\left\{1,2\right\},v\in C$	(LP3)
	$\displaystyle 0\leq x_{t}(i,v),y(i)\leq 1$	$\displaystyle\forall t\in\left\{1,2\right\},v\in C,i\in F$

Given a solution $(x_{1},x_{2},y)$ of LP, we first make the following assumption which follows from facility splitting arguments due to Chudak and Shmoys [27] (see also [58])

Assumption 8.

$\forall t\in\left\{1,2\right\},v\in C,i\in F$ , $x_{t}(i,v)\in\left\{0,y(i)\right\}$ .

We now perform a filtering step inherent to almost all LP-rounding algorithms for $k$ -median. For our problem, as in the $k$ -supplier problem from previous section, we get two sets of “representatives” instead of one that $k$ -median rounding algorithms get.

Filtering.

For $t\in\left\{1,2\right\}$ and any client $v\in C$ , define $C_{t}(v):=\sum_{i\in F}d_{t}(i,v)x_{t}(i,v)$ , i.e. the cost paid by $v$ under metric $d_{t}$ . Our filtering algorithm begins with all clients in an uncovered set $U$ . We pick $j\in U$ with the smallest $C_{t}(j)$ , and call it a representative under $d_{t}$ , adding it to the set $\mathsf{Reps}_{t}$ . Every uncovered client $v$ that is within distance $4C_{t}(v)$ of $j$ becomes a child of $j$ under $d_{t}$ , forming the set $\mathsf{child}_{t}(j)$ . All of $\mathsf{child}_{t}(j)$ is then considered covered. We repeat this until all clients are covered. So we get $\mathsf{Reps}_{t}\subseteq C$ that is well-separated, i.e. any two distinct $j,j^{\prime}\in\mathsf{Reps}_{t}$ have $d_{t}(j,j^{\prime})>4\max\left\{C_{t}(j),C_{t}(j^{\prime})\right\}$ . $\mathsf{Reps}_{t}$ also induces a partition $\left\{\mathsf{child}_{t}(j)\right\}_{j\in\mathsf{Reps}_{t}}$ of $C$ . The following lemma is standard (see the full version [16] for a proof), and thereafter, we focus on $\mathsf{Reps}_{1}$ and $\mathsf{Reps}_{2}$ , and seek a constant-factor approximation on those clients only.

Lemma 9.

Consider $S\subseteq F$ and $\alpha\geq 1$ , such that $\forall t\in\left\{1,2\right\}$ ,
$\sum_{j\in\mathsf{Reps}_{t}}\left\lvert\mathsf{child}_{t}(j)\right\rvert d_{t}% (j,S)\leq\alpha\cdot\sum_{v\in C}C_{t}(v)$ . Then $\mathrm{aggcost}(S)\leq(4+\alpha)\cdot\mathtt{opt}$ .

The rounding algorithms for many $k$ -median algorithms first round to a half-integral solution and then to integral. We follow the same route, and in particular, follow Swamy’s framework [57]. We begin with the following definitions for each $t\in\left\{1,2\right\},j\in\mathsf{Reps}_{t}$ ; as in the previous section, we use $B_{t}(a,r)=\left\{b\in F\cup C:d_{t}(a,b)\leq r\right\}$ . An illustrative figure for these appears in Swamy’s work [57, Figure 1].

$\blacksquare$

$F_{j}^{t}:=\left\{i\in F:d_{t}(i,j)=\min_{j^{\prime}\in\mathsf{Reps}_{t}}d_{t}% (i,j^{\prime})\right\}$ (breaking ties arbitrarily)
$\blacksquare$

$B_{j}^{t}:=B_{t}(j,2C_{t}(j))\cap F$ . Notice that, by construction of $\mathsf{Reps}_{t}$ , $B_{j}^{t}\subseteq F_{j}^{t}$ (also follows from Fact 10).
$\blacksquare$

$\gamma_{j}^{\left(t\right)}:=\min_{i\notin F_{j}^{t}}d_{t}(i,j)$ , and $G_{j}^{t}:=\left\{i\in F_{j}^{t}:d_{t}(i,j)\leq\gamma_{j}^{\left(t\right)}\right\}$ .

We obtain the following a la [57] (see the full version [16] for a proof).

Fact 10.

For every $t\in\left\{1,2\right\},j\in\mathsf{Reps}_{t}$ , we have

$\blacksquare$

$y(B_{j}^{t}):=\sum_{i\in B_{j}^{t}}y(i)\geq\frac{1}{2}$
$\blacksquare$

$B_{j}^{t}\subseteq G_{j}^{t}$
$\blacksquare$

Suppose $\gamma_{j}^{\left(t\right)}=d_{t}(i_{\gamma},j)$ , s.t. $i_{\gamma}\in F^{t}_{\ell}$ . Then $\forall i\in B_{\ell}^{t},d_{t}(i,j)\leq 3\gamma_{j}^{\left(t\right)}$ .

Also note that by design the $F_{j}^{t}$ ’s (and therefore the $G_{j}^{t}$ ’s) are pairwise disjoint for a fixed $t$ when we consider $j\in\mathsf{Reps}_{t}$ . These play the role of the “partitions” as in the $k$ -supplier problem, and our tractability follows because we have only two $t$ ’s. Instead of finding the “largest cardinality independent set”, as we did for the $k$ -supplier problem, we instead find a point maximizing a suitable linear function. Towards this, we describe a “linear function” that acts as a proxy for $C_{t}(j)$ ’s.

For fractional facility masses $z\in[0,1]^{F}$ , $\forall t\in\left\{1,2\right\}$ , and $\forall j\in\mathsf{Reps}_{t}$ , let $z(G_{j}^{t}):=\sum_{i\in G_{j}^{t}}z(i)$ . Then we have

	$\displaystyle T_{t}(z,j):=\sum_{i\in G_{j}^{t}}d_{t}(i,j)z(i)+3\gamma_{j}^{% \left(t\right)}\max\left\{0,1-z(G_{j}^{t})\right\},\,\text{and}$
	$\displaystyle T_{t}(z):=\sum_{j\in\mathsf{Reps}_{t}}\left\lvert\mathsf{child}_% {t}(j)\right\rvert T_{t}(z,j)\,.$

The above definition is quite similar to Swamy’s definition which may be taken as the $T=1$ case, with one difference that we have the “ $\max$ with 0”. When $T=1$ , one can assert $z(G_{j})\leq 1$ but with different $t$ ’s, it may be that $z(G_{j}^{2})>1$ because in metric $1$ we need to open (fractionally) a lot of facilities. Nevertheless, even with the “max” function the following two lemmas similar to those in [57] hold. Their proofs are in the full version [16].

Lemma 11.

Consider $z\in[0,1]^{F}$ s.t. $\forall t\in\left\{1,2\right\},j\in\mathsf{Reps}_{t}$ , $z(B_{j}^{t})\geq\frac{1}{2}$ . Then $j$ ’s assignment cost under $d_{t}$ is at most $T_{t}(z,j)$ . That is, for every $t\in\left\{1,2\right\},j\in\mathsf{Reps}_{t}$ , we can assign variables $\left\{0\leq x^{\prime}_{t}(i,j)\leq z(i)\right\}_{i\in F}$ so that $\sum_{i\in F}d_{t}(i,j)x^{\prime}_{t}(i,j)\leq T_{t}(z,j)$ .

Lemma 12.

For each $t\in\left\{1,2\right\}$ , and each $j\in\mathsf{Reps}_{t}$ , $T_{t}(y,j)\leq 3\cdot C_{t}(j)$ .

Rounding to Half-integral Solution.

We are now ready to describe the algorithm which is encapsulated in the following lemma.

Lemma 13.

There is a polynomial time algorithm that yields a half-integral solution $(\hat{x}_{1},\hat{x}_{2},\hat{y})$ of LP s.t. $\forall t\in\left\{1,2\right\}$ , $\sum_{j\in\mathsf{Reps}_{t}}\left\lvert\mathsf{child}_{t}(j)\right\rvert\sum_{% i\in F}d_{t}(i,j)\hat{x}_{t}(i,j)\leq 6\cdot\sum_{v\in C}C_{t}(v)$ .

Our goal now becomes to find a half-integral $\hat{y}\in\left\{0,\frac{1}{2},1\right\}^{F}$ so that, for each $t\in\left\{1,2\right\}$ , $T_{t}(\hat{y})\leq 6\cdot\sum_{v\in C}C_{t}(v)$ . If we are able to do so, then by Lemma 11 we would be done. To find such a half-intergral solution, we define the following polytope and linearization of $T_{t}$ ’s. The polytope $\mathcal{P}$ has variables $(z,\lambda_{1},\lambda_{2})\in\mathbb{R}_{\geq 0}^{F\cup\mathsf{Reps}_{1}\cup% \mathsf{Reps}_{2}}$ . The auxiliary $\lambda_{t}$ variables serve to linearize the $\max$ terms in the $T_{t}(z)$ ’s, as the constraints in $\mathcal{P}$ ensure that $\lambda_{t}(j)\geq\max\left\{0,1-z(G_{j}^{t})\right\}$ .

	$\displaystyle\mathcal{P}:=\Bigg\{(z,\lambda_{1},\lambda_{2})\in\mathbb{R}_{% \geq 0}^{F\cup\mathsf{Reps}_{1}\cup\mathsf{Reps}_{2}}:$	$\displaystyle z(F)\leq k;\,\forall t\in\left\{1,2\right\},\forall j\in\mathsf{% Reps}_{t},$
		$\displaystyle z(B_{j}^{t})\geq\frac{1}{2},\,z(G_{j}^{t})+\lambda_{t}(j)\geq 1\Bigg\}$

The following follows from the presence of only “two partitions” plus noting the $\lambda$ ’s don’t bother much since they are identity.

Claim 14.

$\mathcal{P}$ has half-integral extreme points.

Proof.

Consider the constraint matrix $M$ of $\mathcal{P}$ . Since the constant terms in the constraints are half-integral, it suffices [40] to show that $M$ is totally unimodular (TU). Indeed, $M$ looks $\left[\begin{array}[]{c|c}\hbox{\multirowsetup$A$}&I\\ &0\end{array}\right]$ where we have the $A$ -matrix corresponding to the $z$ -variables, and the $I$ corresponding to the $\lambda_{t}$ -variables. The dimension of $I$ is $|\mathsf{Reps}_{1}|+|\mathsf{Reps}_{2}|$ . The matrix $A$ is the incidence matrix of two laminar systems – in fact, it is two partitions coarsened by the universe. Such a system is TU [57]. A TU matrix padded with columns with at most one $1$ in them remains TU. $\hfill\vartriangleleft$ Over $\mathcal{P}$ , we can then consider the minimization of the following linearization of the $T_{t}(z)$ ’s: $\forall t\in\left\{1,2\right\},\forall j\in\mathsf{Reps}_{t}$ : $W_{t}(z,\lambda_{t},j):=\sum_{i\in G_{j}^{t}}d_{t}(i,j)z(i)+3\gamma_{j}^{\left% (t\right)}\lambda_{t}(j)$ , and

\displaystyle W_{t}(z,\lambda_{t}):=\sum_{j\in\mathsf{Reps}_{t}}\left\lvert% \mathsf{child}_{t}(j)\right\rvert W_{t}(z,\lambda_{t},j)\,.

The following claim encapsulates that we can find an extreme point of (any polytope) $\mathcal{P}$ which is a $2$ -approximation to both $W_{t}$ ’s simultaneously in a sense made clear below. This allows us to get the desired $\hat{y}$ (as we explain better in the proof of Lemma 13).

Claim 15.

Consider a polytope $\mathcal{P}\subseteq\mathbb{R}_{\geq 0}^{m}$ , linear functions $W_{1},W_{2}:\mathbb{R}^{m}_{\geq 0}\to\mathbb{R}_{\geq 0}$ , and a point $p\in\mathcal{P}$ . There is a polynomial time algorithm which returns an extreme point $\hat{p}$ of $\mathcal{P}$ such that $W_{t}(\hat{p})\leq 2W_{t}(p)$ for $t\in\{1,2\}$ .

Proof.

By Carathéodory’s theorem [15, 56], we can write $p$ as a linear combination of at most $(m+1)$ extreme points of $\mathcal{P}$ . More precisely, we can find, in polynomial time, a subset $\mathcal{E}$ of extreme points such that $|\mathcal{E}|\leq m+1$ and $p=\sum_{q\in\mathcal{E}}\mu_{q}\cdot q$ for some $\mu_{q}$ ’s which form a probability distribution $D_{p}$ . We claim that one of the $q\in\mathcal{E}$ is the desired point, and we can find which one by enumeration. To see why, observe that for $t\in\{1,2\}$ , $\operatorname*{\mathbb{E}}_{\hat{p}\sim D_{p}}[W_{t}(\hat{p})]=W_{t}(p)$ , and so by Markov, $\Pr_{\hat{p}\sim D_{p}}[W_{t}(\hat{p})>2W_{t}(p)]<\frac{1}{2}$ . So, by union bound $\Pr_{\hat{p}\sim D_{p}}[\exists t\in\{1,2\}:\nobreak\ W_{t}(\hat{p})>2W_{t}(p)% ]<1$ implying $\Pr_{\hat{p}\sim D_{p}}[W_{t}(\hat{p})\leq 2W_{t}(p),\nobreak\ \nobreak\ t\in% \{1,2\}]>0$ which proves the above claim. $\hfill\vartriangleleft$

Proof of Lemma 13.

Given our initial solution $(x_{1},x_{2},y)$ of LP, set variables $\lambda_{t}(j):=\max\left\{0,1-y(G_{j}^{t})\right\}$ for each $t\in\left\{1,2\right\}$ , $j\in\mathsf{Reps}_{t}$ . By Fact 10, this gives us $(y,\lambda_{1},\lambda_{2})\in\mathcal{P}$ . So by Claim 14 and Claim 15, we can obtain a half-integral $(\hat{y},\hat{\lambda}_{1},\hat{\lambda}_{2})\in\mathcal{P}$ such that $W_{1}(\hat{y},\hat{\lambda}_{1})\leq 2W_{1}(y,\lambda_{1})$ , and $W_{2}(\hat{y},\hat{\lambda}_{2})\leq 2W_{2}(y,\lambda_{2})$ . So by Lemma 11, for each $t\in\left\{1,2\right\}$ we can construct $\hat{x}_{t}$ ’s such that,

\displaystyle\sum_{j\in\mathsf{Reps}_{t}}\left\lvert\mathsf{child}_{t}(j)% \right\rvert\sum_{i\in F}d_{t}(i,j)\hat{x}_{t}(i,j)

\displaystyle\leq T_{t}(\hat{y})\leq W_{t}(\hat{y},\hat{\lambda}_{t})\leq 2W_{% t}(y,\lambda_{t})

where the penultimate step follows from the constraints in $\mathcal{P}$ . By our construction of the starting $\lambda_{t}$ ’s, i.e. the constraints enforcing $\lambda_{t}(j)\geq\max\{0,1-z(G_{j}^{t})\}$ , $W_{t}(y,\lambda_{t})=T_{t}(y)$ . So we have, by Lemma 12, that the above can be upper bounded by $6\sum_{j\in\mathsf{Reps}_{t}}\left\lvert\mathsf{child}_{t}(j)\right\rvert C_{t% }(j)\leq 6\sum_{v\in C}C_{t}(v)$ . $\hfill\blacktriangleleft$

Rounding to Integral solution.

We round $(\hat{x}_{1},\hat{x}_{2},\hat{y})$ to an integral solution, losing a constant factor, and this is very similar to the ideas in [23, 57]; here also we follow the latter’s framework. We sketch the main ideas here and defer the details to the full version [16].

The first step is another filtering step. For $t\in\{1,2\}$ and $j\in\mathsf{Reps}_{t}$ , define $S^{t}_{j}:=\{i\in F\nobreak\ :\nobreak\ \hat{x}_{t}(i,j)>0\}$ and let $\hat{C}_{t}(j):=\sum_{i\in F}\hat{x}_{t}(i,j)d_{t}(i,j)$ ; note that $\sum_{j\in\mathsf{Reps}_{t}}|\mathsf{child}_{t}(j)|\hat{C}_{t}(j)\leq 6\sum_{v% \in C}C_{t}(v)$ . Now we define a subset of “super-representatives”: we pick $\ell\in\mathsf{Reps}_{t}$ with smallest $\hat{C}_{t}(\ell)$ and add it to $\mathsf{Super}_{t}$ removing every $j$ with $S^{t}_{j}\cap S^{t}_{\ell}\neq\emptyset$ from consideration. In the end, we have $S^{t}_{j}$ ’s pairwise disjoint for $\mathsf{Super}_{t}$ ’s and each $j\in\mathsf{Reps}_{t}$ shares a facility with a super-representative in $\mathsf{Super}_{t}$ .

Next, as in the rounding to the half-integral case, we define a particular linear function which works as a proxy for $\hat{C}_{t}(j)$ . To define this proxy, for every $j\in\mathsf{Reps}_{t}$ call the two facilities in $S^{t}_{j}$ primary and secondary in ascending order of distance (duplicating facilities if needed). For $t\in\{1,2\}$ and $j\in\mathsf{Reps}_{t}$ , let $\ell\in\mathsf{Super}_{t}$ be the super-representative which $j$ shares a facility with, and define

A_{t}(z,j):=\begin{cases}\sum_{i\in S_{\ell}^{t}}d_{t}(i,j)z(i)\hfill\text{if % }\mathsf{prim}_{t}(j)\in S_{\ell}^{t}\\ \sum_{i\in S_{\ell}^{t}}d_{t}(i,j)z(i)+\left(d_{t}(\mathsf{prim}_{t}(j),j)-d_{% t}(\mathsf{sec}_{t}(j),j)\right)\cdot z(\mathsf{prim}_{t}(j))&\text{otherwise}% \end{cases}

It’s instructive to think of all $z(i)$ ’s as $1/2$ ; in that case $A_{t}(z,j)$ is either the average of $j$ ’s distance to $\ell$ ’s facilities when $j$ ’s closest facility is shared with $\ell$ , or it is the average of $j$ ’s distance to it closest facility and distance to the other facility that $\ell$ goes to whom $j$ doesn’t share. The importance of the above function is captured in a couple of observations: (A) for any $t$ and any $j\in\mathsf{Reps}_{t}$ , we can upper bound $A_{t}(\hat{y},j)\leq 2\hat{C}_{t}(j)$ , that is, $A_{t}(\hat{y},j)$ isn’t too bad a proxy, and perhaps more usefully (B) given any $z$ such that $z(S^{t}_{\ell})=1$ for all super representatives, we can find an assignment of any $j\in\mathsf{Reps}_{t}$ to facilities with connection cost $\leq A_{t}(z,j)$ . These two facts, and the fact that we can minimize linear functions over the intersection of two partition matroids (defined by the $S^{t}_{\ell}$ ’s for $t\in\{1,2\}$ and $\ell\in\mathsf{Super}_{t}$ ), gives us an $O(1)$ -approximation. This is because the relevant polytope has integral extreme points (see the full version [16] for a proof). Observation (A) holds because we can charge $j$ ’s journey to $\ell$ ’s “other facility” to $\ell$ ’s connection cost which is smaller than $j$ ’s cost by design; this uses half-intergrality. The details are in the full version [16]. Observation (B) is immediate if $\mathsf{prim}_{t}(j)\in S_{\ell}^{t}$ or if $z(\mathsf{prim}_{t}(j))=0$ ; otherwise, if $z(\mathsf{prim}_{t}(j))=1$ then $j$ will travel to its closest facility while $A_{t}(z,j)$ will be average of two number which are larger than the minimum. The statement is in fact true for fractional $z$ ’s as well and the proof is in the full version [16].

All in all, we get the following theorem; the factor $28$ could definitely be improved, but perhaps no better than $8$ using these methods.

Theorem 16.

When $T=2$ , there is a polynomial time $28$ -approximation algorithm for sum-aggregate $k$ -median.

$\blacktriangleright$ Remark 17 (Generalizing to arbitrary norm aggregators).

In the above proof, we note that the solution $S$ we return has the property that $\mathrm{cost}(d_{t};S)\leq 28\sum_{j\in C}C_{t}(j)$ , for $t\in\{1,2\}$ . This allows us to generalize the above theorem for any aggregator $\Psi$ which is a norm. Instead of a linear program, we would have a convex program. More precisely, we have variables $C_{1},C_{2}$ where $C_{t}:=\sum_{j\in C}C_{t}(j)$ and the objective would minimize $\Psi(C_{1},C_{2})$ . By the property of our rounding and the homogeneity of $\Psi$ , we would get that $\Psi(\mathrm{cost}(d_{1};S),\mathrm{cost}(d_{2};S))\leq 28\Psi(C_{1},C_{2})% \leq 28\mathtt{opt}$ .

$\blacktriangleright$ Remark 18 (Generalizing $(k,z)$ -clustering).

The above theorem focused on the $k$ -median problem. However, the same methodology also gives an $O(1)$ -approximation for the $\Psi$ -aggregated $(k,z)$ -clustering problem due to the fact that we only use triangle inequalities over “bounded number of hops”. This is a folklore observation (see, for instance, Footnote 1 in [21]). To obtain this, first we replace $d_{t}(i,j)$ with $d_{t}(i,j)^{z}$ in the linear/convex program. Next, we use the “relaxed triangle inequality”, which follows from Lemma A.1 in [51], that says if we have $r+1$ points $a_{1},\ldots,a_{r+1}$ , then $d(a_{1},a_{r+1})^{z}\leq r^{z-1}\sum_{i=1}^{r}d(a_{i},a_{i+1})^{z}$ . In our proof above, we never invoke the triangle inequality on more than $4$ points, and thus, everything goes through with a “hit” of $3^{z-1}$ . Note, though, that the definition of the proxy function $T_{t}(z,j)$ would have $3$ replaced by $3^{z}$ . In the end, we would get a $O(1)^{z}$ approximation to the sum of the $z$ th powers, and since we take the $z$ th root, this gives a $O(1)$ -approximation.

4 FPT( $𝒌, 𝑻$ ) constant factor approximation

Theorem 19.

For any homogenous aggregator $\Psi$ , any $z\in\mathbb{N}\cup\left\{\infty\right\}$ , and any constant error parameter $\varepsilon>0$ , there is an algorithm that computes a $(3+\varepsilon)$ -approximate solution to $\Psi$ -aggregate $(k,z)$ -clustering in time $O(\varepsilon^{-1}k)^{O(kT)}\cdot 2^{O(k^{2}T^{2})}\cdot\mathrm{poly}(n)$ .

Proof.

We adapt an existing FPT $3$ -approximation [30, Section 2.1] for standard $(k,z)$ -clustering (i.e. $T=1$ ). Fix an error parameter $\varepsilon>0$ . In our aggregate cluster instance, let $C$ denote the client set and let $F$ denote the facilities. For each scenario $t\in[T]$ (defined by a metric $d_{t}$ and a client weights $w_{t}$ ), we first compute a coreset $C_{t}\subseteq C$ of size $O(\varepsilon^{-2}k\log n)$ [35]; that is, obtain a new client set $C_{t}$ and new weights $w^{\prime}_{t}$ on $C_{t}$ with the property that for any subset of facilities $S\subseteq F$ ,

\sum_{u\in C_{t}}w^{\prime}_{t}(u)\cdot d_{t}(u,S)\in(1\pm\varepsilon)\cdot% \sum_{v\in C}w_{t}(v)\cdot d_{t}(v,S)\,.

Henceforth we work with the coresets $C_{t}$ rather than the entire client set $C$ in each metric.

Let $\mathtt{OPT}\subseteq F$ be the optimal solution to the aggregate clustering instance, with (unknown) centers $o_{1},\dots,o_{k}$ . For an $i\in[k]$ and $t\in[T]$ , let $C_{i,t}$ be the cluster served by $o_{i}$ under $d_{t}$ . Define the client $\ell_{i,t}$ to be the closest client (in the coreset $C_{t}$ ) to $o_{i}$ , that is $d_{t}(o_{i},C_{i,t})=d_{t}(o_{i},\ell_{i,t})$ , and define $r_{i,t}\coloneqq d_{t}(o_{i},\ell_{i,t})$ .

For each scenario $t\in[T]$ and index $i\in[k]$ , we can guess (by enumeration) the client $\ell_{i,t}$ in time $\genfrac{(}{)}{0.0pt}{1}{O(\varepsilon^{-2}k\log n)}{k}$ . We can’t guess $r_{i,t}$ exactly, but we can guess it up to the closest power of $(1+\varepsilon)$ : we assume WLOG (up to a $1+\varepsilon$ loss in the approximation factor) that the aspect ratio of $d_{t}$ is $\mathrm{poly}(n)$ , and so bucketing pairwise distances of $d_{t}$ by powers of $(1+\varepsilon)$ reduces the number of possible distances to $O(\log_{1+\varepsilon}n)=O(\varepsilon^{-1}\log n)$ . Overall, in time $(\genfrac{(}{)}{0.0pt}{1}{O(\varepsilon^{-2}k\log n)}{k}\cdot O(\varepsilon^{-% 1}\log n)^{k})^{T}$ , we can guess each $\ell_{i,t}$ and $r_{i,t}$ . By Fact 26, this overhead is $O(\varepsilon^{-1}k)^{O(kT)}\cdot 2^{O(k^{2}T^{2})}\cdot\mathrm{poly}(n)$ $=O_{\varepsilon,k,T}(1)\cdot\mathrm{poly}(n)$ .

Suppose our guesses are correct. For each $i\in[k]$ , consider the set $F_{i}$ containing the facilities that are within distance $r_{t,t}$ of $\ell_{i,t}$ in every metric $d_{t}$ , i.e. $F_{i}:=\cap_{t=1}^{T}B_{t}(\ell_{i,t},r_{i,t})\cap F$ . If our guesses are correct, then $F_{i}$ is non-empty since $o_{i}$ lies in this intersection. Let our solution $\mathtt{ALG}$ consist of an arbitrary $f_{i}\in F_{i}$ for each $i\in[k]$ . For a client $v$ in the cluster $C_{i,t}$ , we have $d_{t}(o_{i},\ell_{i,t})\leq d_{t}(v,o_{i})$ by definition of $\ell_{i,t}$ ; and also $d_{t}(\ell_{i,t},f_{i})\leq(1+O(\varepsilon))\cdot r_{i,t}=(1+O(\varepsilon))% \cdot d_{t}(\ell_{i,t},o_{i})$ . Using these, we get

	$\displaystyle d_{t}(v,\mathtt{ALG})$	$\displaystyle\leq d_{t}(v,f_{i})\leq d_{t}(v,o_{i})+d_{t}(o_{i},\ell_{i,t})+d_% {t}(\ell_{i,t},f_{i})$
		$\displaystyle\leq d_{t}(v,o_{i})+(2+O(\varepsilon))\cdot d_{t}(o_{i},\ell_{i,t% })\leq(3+O(\varepsilon))\cdot d_{t}(v,o_{i})$

for every $v\in C$ and $t\in[T]$ . Since the $(k,z)$ -clustering cost and the aggregator $\Psi$ are both homogeneous functions, this yields a $(3+O(\varepsilon))$ -approximation. Rescaling $\varepsilon$ by a constant yields the desired result. $\hfill\blacktriangleleft$

In the special case of $k$ -supplier, we have a simpler $(3+\varepsilon)$ -algorithm that doesn’t utilize coresets, and runs in $O(\varepsilon^{-O(T^{2})})\cdot O(k)^{O(kT)}\cdot\mathrm{poly}(n)$ time. We present it in the full version [16].

5 FPT Approximations in Well-structured Metrics

5.1 Metrics with Bounded Scatter Dimension

In this section, we study aggregate clustering in the case where all the $T$ metrics have bounded $\varepsilon$ -scatter dimension. This notion of metric dimension was originally introduced by [1] to obtain $O_{k,\varepsilon}(1)\cdot\mathrm{poly}(n)$ -time $(1+\varepsilon)$ -approximation algorithms (ie, efficient parameterized approximation schemes, or EPASes for short) for a large class of center-based $k$ -clustering problems, for example the $T=1$ case of $(k,z)$ -clustering.

Definition 20 ( $\varepsilon$ -scattering, $\varepsilon$ -scatter dimension [1, Definition IV.1]).

An $\varepsilon$ -scattering in a metric space $M=(C\cup F,d)$ is a sequence $(x_{1},p_{1}),(x_{2},p_{2}),\dots,(x_{l},p_{l})$ s.t.

$\blacksquare$

$\forall i\in[l]$ , $x_{i}\in F$ and $p_{i}\in C$ ;
$\blacksquare$

[covering] $\forall 1\leq j<i\leq l$ , $d(x_{i},p_{j})\leq 1$ ; and
$\blacksquare$

[ $\varepsilon$ -refutation] $\forall i\in[l]$ , $d(x_{i},p_{i})>1+\varepsilon$ .

The $\varepsilon$ -scatter dimension of a family of metric spaces $\mathcal{M}$ is the maximum length of any $\varepsilon$ -scatter of an $M\in\mathcal{M}$ .

A key component of the ( $T=1$ ) EPASes of [1] is an EPAS for the special case of unweighted $k$ -supplier. We recall their algorithm, following their presentation. At a high level, they maintain a $k$ -sized solution $X\subseteq F$ , and while this solution is not a $(1+\varepsilon)$ -approximation, clients with high cost are identified to guide a recomputation of $X$ ; the bounded $\varepsilon$ -scatter dimension is used to show a bound on the number of recomputations needed. In more detail, $X$ is initialized arbitrarily as $X=\left\{x_{1},\dots,x_{k}\right\}$ . Empty buckets $B_{1},\dots,B_{k}$ are also initialized, corresponding to clusters that would eventually be served by $x_{1},\dots,x_{k}$ respectively. We assume we know the cost $\mathtt{opt}$ of the optimal solution⁶⁶6We can approximate it by bucketing by powers of $1+\varepsilon$ and guessing over the $O(\varepsilon^{-1}\log n)$ options.. While there exists a client violating the desired $(1+\varepsilon)$ -approximation of $\mathtt{opt}$ – i.e. while $\exists v\in C:d(v,X)>(1+\varepsilon)\mathtt{opt}$ – the algorithm guesses the index $i\in[k]$ of the optimal cluster that serves $v$ in $\mathtt{OPT}$ . The client $v$ is then placed in the bucket $B_{i}$ , and $x_{i}$ is recomputed so that $\forall u\in B_{i},d(u,x_{i})\leq\mathtt{opt}$ . If such an $x_{i}$ cannot be obtained, then the algorithm asserts failure and restarts from the initialization; but with positive probability $1/k$ we don’t fail (because with probability $1/k$ we guess $i$ correctly). Now here is the key insight, that each bucket $B_{i}$ can’t grow too large. Indeed, consider the sequence of requests $(v_{i}^{(1)},\ldots,v_{k}^{(\ell)})$ added to $B_{i}$ over time, and consider the sequence of candidate locations for $x_{i}$ over time, $(x_{i}^{(1)},\ldots,x_{i}^{(\ell)})$ . These two sequences form an $\varepsilon$ -scatter (after we normalize distances so $\mathtt{opt}=1$ ). In particular, if the $\varepsilon$ -scatter dimension of $d$ is upper-bounded by some $\lambda(\varepsilon)$ , then every bucket $B_{i}$ only grows to size $\lambda(\varepsilon)$ until we either assert success or failure. As there there are $k$ buckets overall, each iteration of the algorithm requires at most $k\lambda(\varepsilon)$ random choices each of which is correct with probability $1/k$ ; so with constant probability, we successfully find a solution after $O_{\varepsilon,k}(1)$ re-initializations.

For our aggregate clustering problem, we generalize the above. Rather than guessing a single partition of the clients into clusters served by $x_{1},\ldots,x_{k}$ , we need to guess $T$ different partitions, one for each metric: we now have buckets $B_{i,t}$ for each $i\in[k],t\in[T]$ , and we separately guess $\mathtt{opt}_{t}=\mathrm{cost}(d_{t};\mathtt{OPT})$ for each $t$ . These metric-wise buckets allows us to mostly decouple the different metrics: when we find a violation in metric $d_{t}$ , i.e. get $\mathrm{cost}(d_{t};X)>(1+\Theta(\varepsilon))\mathtt{opt}_{t}$ , we select a random index $i\in[k]$ and add to bucket $B_{i,t}$ , just as is done for the $T=1$ case. Only when recomputing $x_{i}$ do we take the other metrics into account; we choose $x_{i}$ to obey the constraints of all the buckets $B_{i,t}$ across all $t\in[T]$ , that is $\forall t\in[T]\forall u\in B_{i,t},d_{t}(u,x_{i})\leq\mathtt{opt}_{t}$ . Observe that each bucket $B_{i,t}$ still has bounded size, as it provides witness of an $\varepsilon$ -scatter in metric $d_{t}$ . To be precise, if one considers the sequence of requests $(v_{i}^{(1)},\ldots,v_{i}^{(\ell}))$ in $B_{i,t}$ and the sequence of candidate positions for $x_{i}$ at the moment immediately before request $v_{i}^{j}$ was added⁷⁷7We remark that, unlike the $T=1$ case, the center $x_{i}$ could take on more than $\ell$ candidate positions, because the the position of $x_{i}$ could be changed due to a request in any bucket $B_{i,t^{\prime}}$ for $t^{\prime}\in[T]$ ; nevertheless, even if $x_{i}$ is changed due to a different bucket $B_{i,t^{\prime}}$ we still guarantee that $x_{i}$ covers requests in $B_{i,t}$ , and so one can construct an $\varepsilon$ -scatter., $(x_{i}^{(1)},\ldots,x_{i}^{(\ell)})$ , then these sequences form an $\varepsilon$ -scatter for $d_{t}$ . In particular, each iteration of the algorithm makes $kT\lambda(\varepsilon)$ random choices, and so it succeeds with constant probability after $O_{\varepsilon,k,T}(1)$ rounds.

Theorem 21.

When all $T$ metrics have $\varepsilon$ -scatter dimension at most $\lambda(\varepsilon)$ , for any homogeneous aggregator $\Psi$ there is an algorithm for $\Psi$ -aggregate (unweighted) $k$ -supplier runs in time $O_{\varepsilon,k,T}(1)\cdot\mathrm{poly}(n)$ , and produces a $(1+\varepsilon)$ -approximation with constant probability.

When $T=1$ , the $k$ -supplier EPAS generalizes [1] to weighted $k$ -center (by initializing with the help of a $O(1)$ -approximation), then to weighted $k$ -median (by a random sampling argument), and then to more general $k$ -clustering problems. We adapt some of these ideas to the aggregate setting, and prove the following theorem in the full version [16].

Theorem 22.

When all $T$ metrics have $\varepsilon$ -scatter dimensions upper-bounded by some $\lambda(\varepsilon)$ , for any homogeneous aggregator $\Psi$ there is an algorithm for $\Psi$ -aggregate $k$ -median that runs in time $O_{\varepsilon,k,T}(1)\cdot\mathrm{poly}(n)$ , and produces $(1+\varepsilon)$ -approximations with constant probability.

$\blacktriangleright$ Remark 23 (Barrier at algorithmic scatter dimension).

The authors of [1] also consider a weaker notion of algorithmic $\varepsilon$ -scatter dimension (where, roughly speaking, the length of $\varepsilon$ -scatters are only bounded if the sequence of centers $x_{i}$ is chosen according to a certain algorithm), and their EPASes extend to metrics of bounded algorithmic scatter dimension. For example in the case of $k$ -supplier, when recomputing the center $c_{i}$ for some bucket $B_{i}$ , they just use the algorithm for computing the center rather than choosing $x_{i}$ to be an arbitrary point that covers $B_{i}$ . We are aware of two follow-up works [38, 12] that build on the framework of [1], both of which apply also for algorithmic scatter dimension. In contrast, our aggregate algorithm does not extend to the more general setting; this is because we recompute $x_{i}$ in a way that covers all the buckets $B_{i,t}$ across $t\in[T]$ (and such an $x_{i}$ is guaranteed to exist, if we guessed the buckets correctly), whereas an algorithmic version would require that $x_{i}$ was chosen to simultaneously satisfy the algorithms of all $T$ metrics (and such an $x_{i}$ does not necessarily exist).

5.2 Bounded-treewidth Graphs

Theorem 24.

When the base graph $G$ has treewidth $\mathsf{tw}$ and the aggregator $\Psi=$ sum, then:

$\blacksquare$

there is an exact algorithm for sum-aggregate $(k,z)$ -clustering that runs in time $n^{O(T\cdot\mathsf{tw})}$ .
$\blacksquare$

for any $\varepsilon>0$ , there is a $(1+\varepsilon)$ -approximation algorithm for sum-aggregate $(k,z)$ -clustering that runs in time $(\frac{\log n}{\varepsilon})^{O(T\cdot\mathsf{tw})}\cdot\mathrm{poly}(n)=O_{% \varepsilon,T,\mathsf{tw}}(1)\cdot\mathrm{poly}(n)$ .

In this section we focus on the $k$ -median case; the ideas extend naturally to $(k,z)$ -clustering and $k$ -supplier. We prove Theorem 24 by adapting a folklore dynamic program for solving $k$ -median on bounded-treewidth graphs. (Recall that a tree decomposition of a graph $G$ is a tree $\mathcal{T}$ of bags, where each bag is a subset of vertices $V(G)$ , that satisfies two properties: (1) for every edge $(u,v)$ in $G$ , there is a bag containing both $u$ and $v$ , and (2) for every vertex $v$ in $V(G)$ , the bags containing $v$ induce a connected subtree of $\mathcal{T}$ . The width of the tree decomposition is 1 less than the maximum bag size, and the treewidth of a graph is the minimum width of any tree decoposition. A tree has treewidth 1.) To the best of our knowledge, the DP for $k$ -median has not been written down explicitly in the setting of bounded treewidth graphs, but the technique is standard. Our presentation is based on a DP that appeared [6, 42, 29] as part of a PTAS for $k$ -median in Euclidean metrics. In this section we explain the main idea of the algorithm and defer the formal details to the full version [16].

We begin by reviewing the folklore DP. Every bag $B$ of the tree decomposition $\mathcal{T}$ acts as a small separator between an “inside” piece (induced by the vertices in the subtree of $\mathcal{T}$ rooted at $B$ ) and an “outside” piece (induced by all vertices outside the subtree rooted at $B$ ). For each separator, the DP guesses the interface of the optimal solution $\mathtt{OPT}$ between the two pieces. In the case of $k$ -median, the interface of bag $B=\left\{v_{1},\ldots,v_{\mathsf{tw}}\right\}$ consists of the distance of every $v_{i}$ to the closest open center in the inside (resp. outside) piece, as well as the number of centers opened in the inside (resp. outside) piece in the optimal solution. Note that there are $n^{O(\mathsf{tw})}$ possible interfaces for any bag, as there are $O(n^{2})$ possible distances for each $v_{i}$ ; by rounding distances to the nearest power of $(1+\frac{\varepsilon}{\log n})$ , we could reduce the number of interfaces to $(\frac{\log n}{\varepsilon})^{O(\mathsf{tw})}$ . The DP table contains a cell for every bag $B$ and every possible interface of $B$ , where the value of the cell represents the cost paid by vertices in the inside piece under the best solution that respects the interface. The value of a DP cell at bag $B$ can be computed from the DP cells of the children of $B$ , by taking a minimum over all combinations of children interfaces which are consistent with the interface of $B$ (checking the consistency of interfaces can be done in a straightforward manner in polynomial time [6, 29]). The overall runtime is $n^{O(\mathsf{tw})}$ , or $(\frac{\log n}{\varepsilon})^{O(\mathsf{tw})}\cdot\mathrm{poly}(n)$ if we tolerate $1+\varepsilon$ approximation.

To adapt the DP to the aggregate setting, we simply change the notion of interface: rather than guessing just one interface, we guess a different interface for each of the $T$ metrics $d_{1},\ldots,d_{T}$ . The cells of our DP table now consist of a bag $B=\left\{v_{1},\ldots,v_{\mathsf{tw}}\right\}$ and a set of $T$ tuples; the $t$ -th tuple consists of the distance with respect to $d_{t}$ of every $v_{i}$ to the closest (with respect to $d_{t}$ ) open center in $\mathtt{OPT}$ in each piece, as well as the cost paid by each piece in the $d_{t}$ metric under $\mathtt{OPT}$ . (Note: the reason that we need to guess a different interface for each metric is that, even though the optimal set of centers $\mathtt{OPT}$ for the aggregate problem stays consistent throughout the $T$ metrics, a vertex $v$ could be served by a different center of $\mathtt{OPT}$ in each different metric $d_{t}$ .) There are $n^{O(T\cdot\mathsf{tw})}$ possible interfaces. The DP can be computed in a bottom-up fashion, as in the non-aggregate setting, for a total runtime of $n^{O(T\cdot\mathsf{tw})}$ . If one allows $1+\varepsilon$ approximation, the runtime improves to $(\frac{\log n}{\varepsilon})^{O(T\cdot\mathsf{tw})}\cdot\mathrm{poly}(n)$ , which is at most $\varepsilon^{-O(T^{2}\cdot\mathsf{tw}^{2})}\cdot\mathrm{poly}(n)=O_{% \varepsilon,T,\mathsf{tw}}(1)\cdot\mathrm{poly}(n)$ (see Fact 26).

$\blacktriangleright$ Remark 25.

Observe that if $\mathsf{tw}=o\left(\frac{\log n}{\log\log n}\right)$ , then Theorem 24 provides a $(1+\varepsilon)$ -approximation algorithm in $2^{o(\log n)\cdot T\cdot\log(1/\varepsilon)}\cdot\mathrm{poly}(n)=O_{% \varepsilon,T}(1)\cdot\mathrm{poly}(n)$ time (by Fact 26).

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. IEEE, 2023. doi:10.1109/FOCS57990.2023.00085.
[2] Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension and provably efficient shortest path algorithms. Journal of the ACM (JACM), 63(5):1–26, 2016. doi:10.1145/2985473.
[3] Ittai Abraham, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 782–793. SIAM, 2010.
[4] Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, and Jie Xue. Clustering what matters: Optimal approximation for clustering with outliers. J. Artif. Int. Res., 78, 2024.
[5] Barbara Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems. Mathematics of Operations Research, 35(1):79–101, 2010. Preliminary version appeared in SODA 2008. doi:10.1287/MOOR.1090.0428.
[6] Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for euclidean k-medians and related problems. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 106–113, 1998. doi:10.1145/276698.276718.
[7] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for $k$ -median and facility location problems. SIAM Journal on Computing (SICOMP), 33(3):544–562, 2004. doi:10.1137/S0097539702416402.
[8] MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In the Symposium on Discrete Algorithms (SODA), pages 2677–2727, 2023. doi:10.1137/1.9781611977554.CH101.
[9] Sayan Bhattacharya, Martín Costa, and Ermiya Farokhnejad. Fully dynamic $k$ -median with near-optimal update time and recourse. In the Symposium on Theory of Computing (STOC), pages 1166–1177, 2025. doi:10.1145/3717823.3718176.
[10] Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic $k$ -clustering in $\tilde{O}(k$ update time. Adv. in Neural Infomation Processing Systems (NeurIPS), 36:18633–18658, 2023.
[11] Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic $k$ -center clustering made simple. In the International Conference on Machine Learning (ICML), 2025.
[12] Sujoy Bhore, Ameet Gadekar, and Tanmay Inamdar. Coreset strikes back: Improved parameterized approximation schemes for (constrained) k-median/means. arXiv preprint arXiv:2504.06980, 2025. doi:10.48550/arXiv.2504.06980.
[13] Romain Bourneuf and Marcin Pilipczuk. Bounding $\varepsilon$ -scatter dimension via metric sparsity. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3155–3171. SIAM, 2025. doi:10.1137/1.9781611978322.101.
[14] Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for $k$ -median, and positive correlation in budgeted optimization. In the Symposium on Discrete Algorithms (SODA), pages 737–756, 2014.
[15] Constantin Carathéodory. Über den variabilitätsbereich der fourier’schen konstanten von positiven harmonischen funktionen. Rendiconti Del Circolo Matematico di Palermo (1884-1940), 32(1):193–217, 1911.
[16] Deeparnab Chakrabarty, Jonathan Conroy, and Ankita Sarkar. Clustering in varying metrics, 2025. arXiv:2510.07860.
[17] Deeparnab Chakrabarty, Luc Cote, and Ankita Sarkar. Fault-tolerant k-supplier with outliers. In the Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.STACS.2024.23.
[18] Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The Non-Uniform $k$ -Center Problem. the ACM Transactions on Algorithms (TALG), 2020. Preliminary version in ICALP 2016. doi:10.1145/3392720.
[19] Deeparnab Chakrabarty and Maryam Negahbani. Generalized Center Problems with Outliers. the ACM Transactions on Algorithms (TALG), 2019. Prelim. version in ICALP 2018. doi:10.1145/3338513.
[20] Deeparnab Chakrabarty, Maryam Negahbani, and Ankita Sarkar. Approximation algorithms for continuous clustering and facility location problems. In European Symposium on Algorithms, 2022.
[21] Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In the Symposium on Theory of Computing (STOC), pages 126–137, 2019. doi:10.1145/3313276.3316322.
[22] TH Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dynamic k-center clustering. In the International World Wide Web Conference, pages 579–587, 2018.
[23] Moses Charikar, Sudipto Guha, Éva Tardos, and David B Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129–149, 2002. Preliminary version appeared in STOC 1999. doi:10.1006/JCSS.2002.1882.
[24] Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In the Symposium on Discrete Algorithms (SODA), volume 1, pages 642–651. Citeseer, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365555.
[25] Moses Charikar and Shi Li. A dependent lp-rounding approach for the k-median problem. In International Colloquium on Automata, Languages, and Programming, pages 194–205. Springer, 2012. doi:10.1007/978-3-642-31594-7_17.
[26] Eden Chlamtáč, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In the Symposium on Discrete Algorithms (SODA), 2022.
[27] Fabián A Chudak and David B Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. Journal of the ACM (JACM), 33(1):1–25, 2003. doi:10.1137/S0097539703405754.
[28] Julia Chuzhoy and Zihan Tan. Towards tight (er) bounds for the excluded grid theorem. Journal of Combinatorial Theory, Series B, 146:219–265, 2021. doi:10.1016/J.JCTB.2020.09.010.
[29] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. Journal of the ACM (JACM), 68(6):1–34, 2021. doi:10.1145/3477541.
[30] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight fpt approximations for k-median and k-means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 42–1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.
[31] Vincent Cohen-Addad, Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. Adv. in Neural Infomation Processing Systems (NeurIPS), 32, 2019.
[32] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[33] Shichuan Deng, Jian Li, and Yuval Rabani. Approximation algorithms for clustering with dynamic points. Journal of Computer and System Sciences, 130:43–70, 2022. doi:10.1016/J.JCSS.2022.07.001.
[34] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634–652, 1998. doi:10.1145/285055.285059.
[35] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569–578, 2011. doi:10.1145/1993636.1993712.
[36] Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Consistent k-clustering for general metrics. In the Symposium on Discrete Algorithms (SODA), pages 2660–2678, 2021. doi:10.1137/1.9781611976465.158.
[37] Sebastian Forster and Antonis Skarlatos. Dynamic consistent k-center clustering with optimal recourse. In the Symposium on Discrete Algorithms (SODA), pages 212–254, 2025. doi:10.1137/1.9781611978322.7.
[38] Ameet Gadekar and Tanmay Inamdar. Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering. In Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyên Kim Thang, editors, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2025.35.
[39] Dorit S Hochbaum and David B Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM (JACM), 33(3):533–550, 1986. doi:10.1145/5925.5933.
[40] AJ Hoffman and JB Kruskal. Integral boundary points of convex polyhedra, in “linear inequalities and related systems”(hw kuhn and aw tucker, eds.). Annals of Mathematical Studies, 38, 1956.
[41] Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and $k$ -median problems using the primal-dual schema and Lagrangean relaxation. Journal of the ACM (JACM), 48(2):274–296, 2001. doi:10.1145/375827.375845.
[42] Stavros G Kolliopoulos and Satish Rao. A nearly linear-time approximation scheme for the euclidean k-median problem. SIAM Journal on Computing, 37(3):757–782, 2007. doi:10.1137/S0097539702404055.
[43] Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In the Symposium on Theory of Computing (STOC), pages 646–659, 2018. doi:10.1145/3188745.3188882.
[44] Shrinu Kushagra. Three-dimensional matching is np-hard. arXiv preprint arXiv:2003.00336, 2020. arXiv:2003.00336.
[45] Shrinu Kushagra, Shai Ben-David, and Ihab Ilyas. Semi-supervised clustering for de-duplication. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1659–1667. PMLR, 2019. URL: http://proceedings.mlr.press/v89/kushagra19a.html.
[46] Jakub Łącki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, and Václav Rozhoň. Fully dynamic consistent k-center clustering. In the Symposium on Discrete Algorithms (SODA), pages 3463–3484, 2024.
[47] Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In the International Conference on Machine Learning (ICML), pages 1975–1984, 2017. URL: http://proceedings.mlr.press/v70/lattanzi17a.html.
[48] Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45–58, 2013. doi:10.1016/J.IC.2012.01.007.
[49] Shi Li and Ola Svensson. Approximating $k$ -median via pseudo-approximation. SIAM Journal on Computing (SICOMP), 45(2):530–547, 2016. doi:10.1137/130938645.
[50] Sepideh Mahabadi and Ali Vakilian. (Individual) Fairness for $k$ -Clustering. In the International Conference on Machine Learning (ICML), pages 7925–7935, 2020. URL: https://dl.acm.org/doi/abs/10.5555/3524938.3525549.
[51] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of johnson-lindenstrauss transform for k-means and k-medians clustering. In the Symposium on Theory of Computing (STOC), pages 1027–1038, 2019. doi:10.1145/3313276.3316350.
[52] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In the Conference on Learning Theory (COLT), 2021.
[53] 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.
[54] Neil Robertson and Paul D Seymour. Graph minors. v. excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986. doi:10.1016/0095-8956(86)90030-4.
[55] David B Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In the Symposium on Theory of Computing (STOC), pages 265–274, 1997.
[56] Ernst Steinitz. Bedingt konvergente reihen und konvexe systeme. Journal für die reine und angewandte Mathematik, 1913.
[57] Chaitanya Swamy. Improved approximation algorithms for matroid and knapsack median problems and applications. the ACM Transactions on Algorithms (TALG), 12(4):1–22, 2016. doi:10.1145/2963170.
[58] Li Yan and Marek Chrobak. Lp-rounding algorithms for the fault-tolerant facility placement problem. Journal of Discrete Algorithms, 33:93–114, 2015. doi:10.1016/J.JDA.2015.03.004.
[59] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In the International Conference on Machine Learning (ICML), pages 928–936, 2003. URL: http://www.aaai.org/Library/ICML/2003/icml03-120.php.

Appendix A Useful facts

Fact 26.

For any $f(n)=n^{o(1)}$ and any variable $\tau\geq 1$ , the function $(f(n))^{\tau}$ is bounded above by $O_{\tau}(1)+n$ . For example, when $f(n)=\log n$ , we have $(\log n)^{\tau}\leq 2^{\tau^{2}}+n$ .

Proof.

Let $g(n)=\log f(n)$ , and note $g(n)=o(\log n)$ . If $\tau$ satisfies $k\tau\leq\log n$ , then clearly $f(n)^{\tau}\leq n$ . On the other hand, if $\tau>\frac{\log n}{k}$ , then the fact that $g(n)=o(\log n)$ implies that $\tau$ grows as a function of $n$ , and so $f(n)^{\tau}=O_{\tau}(1)$ .

We now give an example that provides explicit bounds for the case $f(n)=\log n$ . If $\tau\leq\log\log n$ , then $(\log n)^{\tau}\leq 2^{(\log\log n)^{2}}\leq n$ . Otherwise, if $\tau>\log\log n$ , then $(\log n)^{\tau}=2^{\tau\log\log n}\leq 2^{\tau^{2}}$ . $\hfill\blacktriangleleft$

Observation 27.

Fix an aggregator function $\Psi$ . Suppose that one can find an $\alpha$ -approximation to the $\Psi$ -aggregate $k$ -supplier (or $k$ -median, or $(k,z)$ -clustering) problem on $T$ metrics and $n$ vertices in time $f(n,T,k,\alpha)$ . Then one can find an $\alpha$ -approximation to generalized aggregate clustering, with the restriction that weights come from $\left\{0,1\right\}$ , in time $f(2n+1,T,k+1,\alpha)+\mathrm{poly}(n,T)$ .

Proof.

Suppose we are given an instance $\eta$ of $\left\{0,1\right\}$ -weighted generalized aggregate $k$ -clustering, defined by metrics $d_{1},\ldots,d_{T}$ , client set $C$ , and facility set $F$ . We construct an instance $\eta^{\prime}$ of vanilla aggregate $(k+1)$ -clustering as follows. Create a new vertex $r$ , and let the new facility set $F^{\prime}$ be $F^{\prime}\coloneqq F\cup\left\{r\right\}$ . The client set $C^{\prime}$ is set to be $C$ . We assume WLOG that $C^{\prime}$ and $F^{\prime}$ are disjoint: if some vertex $v$ is both a client and facility, we duplicate $v$ , and make one copy a client and one a facility. After this duplication, we have $|F^{\prime}\cup C^{\prime}|\leq 2|F\cup C|+1=2n+1$ .

For every $t\in[T]$ , we construct a new distance metric $d^{\prime}_{t}$ as follows. We define the active vertices to be the set of clients with weight 1 in the $t$ -th instance, together with the set of facilities excluding $r$ (that is, $F^{\prime}\setminus\left\{r\right\}=F$ ). The inactive vertices are those clients with weight 0 in the $t$ -th instance, and the facility $r$ . For any two vertices $v_{1},v_{2}\in C\cup F$ , we define

\hat{d}^{\prime}_{t}(v_{1},v_{2})\coloneqq\begin{cases}d_{t}(v_{1},v_{2})&% \text{if $v_{1}$ and $v_{2}$ are both active}\\ \infty&\text{if one of $\left\{v_{1},v_{2}\right\}$ is active and the other is% inactive}\\ 0&\text{if $v_{1}$ and $v_{2}$ are both inactive}\end{cases}

One can compute a solution to the instance $\eta$ from a solution to $\eta^{\prime}$ . Indeed, suppose $S^{\prime}\subseteq F^{\prime}$ is a set of $k+1$ facilities with aggregate cost $\kappa$ in $\eta^{\prime}$ . It is straightforward to see that, if $\kappa^{\prime}$ is finite, then facility $r$ is included in $S^{\prime}$ , and the set $S\coloneqq S^{\prime}\setminus\left\{r\right\}$ has aggregate cost $\kappa$ for the instance $\eta$ . Moreover, if $S\subseteq F$ is any set of $k$ facilities with aggregate cost $\kappa$ in $\eta$ , then the set of facilities $S^{\prime}\coloneqq S\cup\left\{r\right\}$ has aggregate cost $\kappa$ in $\eta^{\prime}$ . This proves the claim: in polynomial time one can construct $\eta^{\prime}$ , and in time $f(2n+1,T,k+1,\alpha)$ one can compute an approximate solution $S^{\prime}$ and return $S^{\prime}\setminus\left\{r\right\}$ . $\hfill\blacktriangleleft$

[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. IEEE, 2023. doi:10.1109/FOCS57990.2023.00085.

[bib.bib2] [2] Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension and provably efficient shortest path algorithms. Journal of the ACM (JACM), 63(5):1–26, 2016. doi:10.1145/2985473.

[bib.bib3] [3] Ittai Abraham, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 782–793. SIAM, 2010.

[bib.bib4] [4] Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, and Jie Xue. Clustering what matters: Optimal approximation for clustering with outliers. J. Artif. Int. Res., 78, 2024.

[bib.bib5] [5] Barbara Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems. Mathematics of Operations Research, 35(1):79–101, 2010. Preliminary version appeared in SODA 2008. doi:10.1287/MOOR.1090.0428.

[bib.bib6] [6] Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for euclidean k-medians and related problems. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 106–113, 1998. doi:10.1145/276698.276718.

[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 Journal on Computing (SICOMP), 33(3):544–562, 2004. doi:10.1137/S0097539702416402.

[bib.bib8] [8] MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In the Symposium on Discrete Algorithms (SODA), pages 2677–2727, 2023. doi:10.1137/1.9781611977554.CH101.

[bib.bib9] [9] Sayan Bhattacharya, Martín Costa, and Ermiya Farokhnejad. Fully dynamic $k$ -median with near-optimal update time and recourse. In the Symposium on Theory of Computing (STOC), pages 1166–1177, 2025. doi:10.1145/3717823.3718176.

[bib.bib10] [10] Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic $k$ -clustering in $\tilde{O}(k$ update time. Adv. in Neural Infomation Processing Systems (NeurIPS), 36:18633–18658, 2023.

[bib.bib11] [11] Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic $k$ -center clustering made simple. In the International Conference on Machine Learning (ICML), 2025.

[bib.bib12] [12] Sujoy Bhore, Ameet Gadekar, and Tanmay Inamdar. Coreset strikes back: Improved parameterized approximation schemes for (constrained) k-median/means. arXiv preprint arXiv:2504.06980, 2025. doi:10.48550/arXiv.2504.06980.

[bib.bib13] [13] Romain Bourneuf and Marcin Pilipczuk. Bounding $\varepsilon$ -scatter dimension via metric sparsity. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3155–3171. SIAM, 2025. doi:10.1137/1.9781611978322.101.

[bib.bib14] [14] Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for $k$ -median, and positive correlation in budgeted optimization. In the Symposium on Discrete Algorithms (SODA), pages 737–756, 2014.

[bib.bib15] [15] Constantin Carathéodory. Über den variabilitätsbereich der fourier’schen konstanten von positiven harmonischen funktionen. Rendiconti Del Circolo Matematico di Palermo (1884-1940), 32(1):193–217, 1911.

[bib.bib16] [16] Deeparnab Chakrabarty, Jonathan Conroy, and Ankita Sarkar. Clustering in varying metrics, 2025. arXiv:2510.07860.

[bib.bib17] [17] Deeparnab Chakrabarty, Luc Cote, and Ankita Sarkar. Fault-tolerant k-supplier with outliers. In the Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.STACS.2024.23.

[bib.bib18] [18] Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The Non-Uniform $k$ -Center Problem. the ACM Transactions on Algorithms (TALG), 2020. Preliminary version in ICALP 2016. doi:10.1145/3392720.

[bib.bib19] [19] Deeparnab Chakrabarty and Maryam Negahbani. Generalized Center Problems with Outliers. the ACM Transactions on Algorithms (TALG), 2019. Prelim. version in ICALP 2018. doi:10.1145/3338513.

[bib.bib20] [20] Deeparnab Chakrabarty, Maryam Negahbani, and Ankita Sarkar. Approximation algorithms for continuous clustering and facility location problems. In European Symposium on Algorithms, 2022.

[bib.bib21] [21] Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In the Symposium on Theory of Computing (STOC), pages 126–137, 2019. doi:10.1145/3313276.3316322.

[bib.bib22] [22] TH Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dynamic k-center clustering. In the International World Wide Web Conference, pages 579–587, 2018.

[bib.bib23] [23] Moses Charikar, Sudipto Guha, Éva Tardos, and David B Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129–149, 2002. Preliminary version appeared in STOC 1999. doi:10.1006/JCSS.2002.1882.

[bib.bib24] [24] Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In the Symposium on Discrete Algorithms (SODA), volume 1, pages 642–651. Citeseer, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365555.

[bib.bib25] [25] Moses Charikar and Shi Li. A dependent lp-rounding approach for the k-median problem. In International Colloquium on Automata, Languages, and Programming, pages 194–205. Springer, 2012. doi:10.1007/978-3-642-31594-7_17.

[bib.bib26] [26] Eden Chlamtáč, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In the Symposium on Discrete Algorithms (SODA), 2022.

[bib.bib27] [27] Fabián A Chudak and David B Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. Journal of the ACM (JACM), 33(1):1–25, 2003. doi:10.1137/S0097539703405754.

[bib.bib28] [28] Julia Chuzhoy and Zihan Tan. Towards tight (er) bounds for the excluded grid theorem. Journal of Combinatorial Theory, Series B, 146:219–265, 2021. doi:10.1016/J.JCTB.2020.09.010.

[bib.bib29] [29] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. Journal of the ACM (JACM), 68(6):1–34, 2021. doi:10.1145/3477541.

[bib.bib30] [30] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight fpt approximations for k-median and k-means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 42–1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.

[bib.bib31] [31] Vincent Cohen-Addad, Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. Adv. in Neural Infomation Processing Systems (NeurIPS), 32, 2019.

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

[bib.bib33] [33] Shichuan Deng, Jian Li, and Yuval Rabani. Approximation algorithms for clustering with dynamic points. Journal of Computer and System Sciences, 130:43–70, 2022. doi:10.1016/J.JCSS.2022.07.001.

[bib.bib34] [34] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634–652, 1998. doi:10.1145/285055.285059.

[bib.bib35] [35] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569–578, 2011. doi:10.1145/1993636.1993712.

[bib.bib36] [36] Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Consistent k-clustering for general metrics. In the Symposium on Discrete Algorithms (SODA), pages 2660–2678, 2021. doi:10.1137/1.9781611976465.158.

[bib.bib37] [37] Sebastian Forster and Antonis Skarlatos. Dynamic consistent k-center clustering with optimal recourse. In the Symposium on Discrete Algorithms (SODA), pages 212–254, 2025. doi:10.1137/1.9781611978322.7.

[bib.bib38] [38] Ameet Gadekar and Tanmay Inamdar. Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering. In Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyên Kim Thang, editors, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2025.35.

[bib.bib39] [39] Dorit S Hochbaum and David B Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM (JACM), 33(3):533–550, 1986. doi:10.1145/5925.5933.

[bib.bib40] [40] AJ Hoffman and JB Kruskal. Integral boundary points of convex polyhedra, in “linear inequalities and related systems”(hw kuhn and aw tucker, eds.). Annals of Mathematical Studies, 38, 1956.

[bib.bib41] [41] Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and $k$ -median problems using the primal-dual schema and Lagrangean relaxation. Journal of the ACM (JACM), 48(2):274–296, 2001. doi:10.1145/375827.375845.

[bib.bib42] [42] Stavros G Kolliopoulos and Satish Rao. A nearly linear-time approximation scheme for the euclidean k-median problem. SIAM Journal on Computing, 37(3):757–782, 2007. doi:10.1137/S0097539702404055.

[bib.bib43] [43] Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In the Symposium on Theory of Computing (STOC), pages 646–659, 2018. doi:10.1145/3188745.3188882.

[bib.bib44] [44] Shrinu Kushagra. Three-dimensional matching is np-hard. arXiv preprint arXiv:2003.00336, 2020. arXiv:2003.00336.

[bib.bib45] [45] Shrinu Kushagra, Shai Ben-David, and Ihab Ilyas. Semi-supervised clustering for de-duplication. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1659–1667. PMLR, 2019. URL: http://proceedings.mlr.press/v89/kushagra19a.html.

[bib.bib46] [46] Jakub Łącki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, and Václav Rozhoň. Fully dynamic consistent k-center clustering. In the Symposium on Discrete Algorithms (SODA), pages 3463–3484, 2024.

[bib.bib47] [47] Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In the International Conference on Machine Learning (ICML), pages 1975–1984, 2017. URL: http://proceedings.mlr.press/v70/lattanzi17a.html.

[bib.bib48] [48] Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45–58, 2013. doi:10.1016/J.IC.2012.01.007.

[bib.bib49] [49] Shi Li and Ola Svensson. Approximating $k$ -median via pseudo-approximation. SIAM Journal on Computing (SICOMP), 45(2):530–547, 2016. doi:10.1137/130938645.

[bib.bib50] [50] Sepideh Mahabadi and Ali Vakilian. (Individual) Fairness for $k$ -Clustering. In the International Conference on Machine Learning (ICML), pages 7925–7935, 2020. URL: https://dl.acm.org/doi/abs/10.5555/3524938.3525549.

[bib.bib51] [51] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of johnson-lindenstrauss transform for k-means and k-medians clustering. In the Symposium on Theory of Computing (STOC), pages 1027–1038, 2019. doi:10.1145/3313276.3316350.

[bib.bib52] [52] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In the Conference on Learning Theory (COLT), 2021.

[bib.bib53] [53] 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.bib54] [54] Neil Robertson and Paul D Seymour. Graph minors. v. excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986. doi:10.1016/0095-8956(86)90030-4.

[bib.bib55] [55] David B Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In the Symposium on Theory of Computing (STOC), pages 265–274, 1997.

[bib.bib56] [56] Ernst Steinitz. Bedingt konvergente reihen und konvexe systeme. Journal für die reine und angewandte Mathematik, 1913.

[bib.bib57] [57] Chaitanya Swamy. Improved approximation algorithms for matroid and knapsack median problems and applications. the ACM Transactions on Algorithms (TALG), 12(4):1–22, 2016. doi:10.1145/2963170.

[bib.bib58] [58] Li Yan and Marek Chrobak. Lp-rounding algorithms for the fault-tolerant facility placement problem. Journal of Discrete Algorithms, 33:93–114, 2015. doi:10.1016/J.JDA.2015.03.004.

[bib.bib59] [59] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In the International Conference on Machine Learning (ICML), pages 928–936, 2003. URL: http://www.aaai.org/Library/ICML/2003/icml03-120.php.

Clustering in Varying Metrics

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1 (Aggregate Clustering Problems).

Definition 2 (Generalized Aggregate Clustering).

1.1 Our Findings

General Metrics.

Constant-factor FPT approximation algorithms.

Approximation schemes in structured metrics.

Open Directions

1.2 Related Works

2 Hardness of Approximation

Theorem 3 (Hardness of approximation when T≥3).

Proof.

Theorem 4.

Theorem 5 (Hardness of approximation on stars in FPT time.).

Proof.

▶ Remark 6.

3 Constant-factor approximations for 𝑻=𝟐 scenarios

3.1 𝟑-approximation for Aggregate 𝒌-Supplier

Theorem 7.

3.2 𝑶⁢(𝟏)-approximation for Aggregate 𝒌-Median

Linear Programming Relaxation

Assumption 8.

Filtering.

Lemma 9.

Fact 10.

Lemma 11.

Lemma 12.

Rounding to Half-integral Solution.

Lemma 13.

Claim 14.

Proof.

Claim 15.

Proof.

Proof of Lemma 13.

Rounding to Integral solution.

Theorem 16.

▶ Remark 17 (Generalizing to arbitrary norm aggregators).

▶ Remark 18 (Generalizing (k,z)-clustering).

4 FPT(𝒌,𝑻) constant factor approximation

Theorem 19.

Proof.

5 FPT Approximations in Well-structured Metrics

5.1 Metrics with Bounded Scatter Dimension

Definition 20 (ε-scattering, ε-scatter dimension [1, Definition IV.1]).

Theorem 21.

Theorem 22.

▶ Remark 23 (Barrier at algorithmic scatter dimension).

5.2 Bounded-treewidth Graphs

Theorem 24.

▶ Remark 25.

References

Appendix A Useful facts

Fact 26.

Proof.

Observation 27.

Proof.

Theorem 3 (Hardness of approximation when $T\geq 3$ ).

$\blacktriangleright$ Remark 6.

3 Constant-factor approximations for $T=2$ scenarios

3.1 $3$ -approximation for Aggregate $𝒌$ -Supplier

3.2 $O(1)$ -approximation for Aggregate $𝒌$ -Median

$\blacktriangleright$ Remark 17 (Generalizing to arbitrary norm aggregators).

$\blacktriangleright$ Remark 18 (Generalizing $(k,z)$ -clustering).

4 FPT( $𝒌, 𝑻$ ) constant factor approximation

Definition 20 ( $\varepsilon$ -scattering, $\varepsilon$ -scatter dimension [1, Definition IV.1]).

$\blacktriangleright$ Remark 23 (Barrier at algorithmic scatter dimension).

$\blacktriangleright$ Remark 25.