Clustering in Varying Metrics

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 $\hat{I}¨$ over the $T$ cost values. We show that for $T\ge 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 $\epsilon$-scatter dimension, we achieve a $(1+\epsilon )$-approximation in $f(k,T,\epsilon )\mathrm{poly}(n)$ time. If the metrics are induced by edge weights on a common graph $G$ of bounded treewidth $\mathsf{tw}$, and $\hat{I}¨$ is the sum function, we get an EPAS in $f(T,\epsilon ,\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}=\hat{I}\text{c◯}(\mathrm{poly}\log n)$.

Accepted to FSTTCS 2025