Options
Approximate minimum tree cover in all symmetric monotone norms simultaneously
Citation Link: https://doi.org/10.15480/882.14837
Publikationstyp
Conference Paper
Date Issued
2025-02-24
Sprache
English
TORE-DOI
First published in
Number in series
327
Article Number
57
Citation
International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
We 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.
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.
DDC Class
004: Computer Sciences
005.1: Programming
519: Applied Mathematics, Probabilities
621.3: Electrical Engineering, Electronic Engineering
Publication version
publishedVersion
Loading...
Name
LIPIcs.STACS.2025.57.pdf
Size
1.25 MB
Format
Adobe PDF