2026-07-22T18:41:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18102 2024-03-06T11:01:01Z ddc:004 open_access

Connected k-Center and k-Diameter Clustering Drexler, Lukas Eube, Jan Luo, Kelin Röglin, Heiko Schmidt, Melanie Wargalla, Julian Approximation algorithms Clustering Connectivity constraints Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graph G on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in G. Usually in clustering problems one assumes that the clusters are pairwise disjoint. We study this case but additionally also the case that clusters are allowed to be non-disjoint. This can help to satisfy the connectivity constraints. Our main result is an O(1)-approximation algorithm for the disjoint connected k-center and k-diameter problem for Euclidean spaces of low dimension (constant d) and for metrics with constant doubling dimension. For general metrics, we get an O(log²k)-approximation. Our algorithms work by computing a non-disjoint connected clustering first and transforming it into a disjoint connected clustering. We complement these upper bounds by several upper and lower bounds for variations and special cases of the model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lukas Drexler and Jan Eube and Kelin Luo and Heiko Röglin and Melanie Schmidt and Julian Wargalla 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.50 urn:nbn:de:0030-drops-181024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.50 eng https://creativecommons.org/licenses/by/4.0/legalcode