Kaul, MatthiasMatthiasKaulLuo, KelinKelinLuoMnich, MatthiasMatthiasMnichRöglin, HeikoHeikoRöglin2025-02-262025-02-262025-02-24International Symposium on Theoretical Aspects of Computer Science (STACS 2025)https://hdl.handle.net/11420/54470We study the problem of partitioning a set of n objects in a metric space into k clusters V1,...,Vk. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the ℓp-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in Vi, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This problem has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using ℓ∞) as Min-Max Tree Cover, for which they gave a constant-factor approximation algorithm. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial-time algorithm computing a constant-factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single ℓp norm for the objective.enhttps://creativecommons.org/licenses/by/4.0/Computer Science, Information and General Works::004: Computer SciencesComputer Science, Information and General Works::005: Computer Programming, Programs, Data and Security::005.1: ProgrammingNatural Sciences and Mathematics::519: Applied Mathematics, ProbabilitiesTechnology::621: Applied Physics::621.3: Electrical Engineering, Electronic EngineeringConference Paperhttps://doi.org/10.15480/882.1483710.4230/LIPIcs.STACS.2025.5710.15480/882.14837Conference Paper