2026-09-18T02:36:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24269 2026-09-05T18:40:17Z ddc:004 open_access

Clustering Point Sets Revisited Hossain, Md. Billal Raichel, Benjamin Clustering k-center k-median k-means In the sets clustering problem one is given a collection of point sets 𝒫 = {P_1,… P_m} in ℝ^d, where for any set of k centers in ℝ^d, each P_i is assigned to its nearest center as determine by some local cost functions. The goal is then to select a set of k centers to minimize some global cost function of the corresponding local assignment costs. Specifically, we consider either summing or taking the maximum cost over all P_i, where for each P_i the cost of assigning it to a center c is either max_{p ∈ P_i} ‖c-p‖, ∑_{p ∈ P_i} ‖c-p‖, or ∑_{p ∈ P_i} ‖c-p‖². Different combinations of the global and local cost functions naturally generalize the k-center, k-median, and k-means clustering problems. In this paper, we improve the prior results for the natural generalization of k-center, give the first result for the natural generalization of k-means, and give results for generalizations of k-median and k-center which differ from those previously studied. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Md. Billal Hossain and Benjamin Raichel 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.38 urn:nbn:de:0030-drops-242693 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.38 eng https://creativecommons.org/licenses/by/4.0/legalcode