{"ID":2857960,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.07860","arxiv_id":"2510.07860","title":"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 $Ψ$ 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 $Ψ$ 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} = Ω(\\mathrm{poly}\\log n)$.","short_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$...","url_abs":"https://arxiv.org/abs/2510.07860","url_pdf":"https://arxiv.org/pdf/2510.07860v1","authors":"[\"Deeparnab Chakrabarty\",\"Jonathan Conroy\",\"Ankita Sarkar\"]","published":"2025-10-09T07:03:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}