TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Approximate minimum tree cover in all symmetric monotone norms simultaneously
 
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
Author(s)
Kaul, Matthias  orcid-logo
Algorithmen und Komplexität E-11  
Luo, Kelin  
Mnich, Matthias  orcid-logo
Algorithmen und Komplexität E-11  
Röglin, Heiko  
TORE-DOI
10.15480/882.14837
TORE-URI
https://hdl.handle.net/11420/54470
First published in
Leibniz international proceedings in informatics (LIPIcs)  
Number in series
327
Article Number
57
Citation
International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
Contribution to Conference
42nd International Symposium on Theoretical Aspects of Computer Science, (STACS 2025)  
Publisher DOI
10.4230/LIPIcs.STACS.2025.57
Scopus ID
2-s2.0-85219541158
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.
DDC Class
004: Computer Sciences
005.1: Programming
519: Applied Mathematics, Probabilities
621.3: Electrical Engineering, Electronic Engineering
Publication version
publishedVersion
Lizenz
https://creativecommons.org/licenses/by/4.0/
Loading...
Thumbnail Image
Name

LIPIcs.STACS.2025.57.pdf

Size

1.25 MB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback