2026-08-18T02:59:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12255 2024-03-06T10:49:27Z ddc:004 open_access

Submodular Clustering in Low Dimensions Backurs, Arturs Har-Peled, Sariel clustering covering PTAS We study a clustering problem where the goal is to maximize the coverage of the input points by k chosen centers. Specifically, given a set of n points P ⊆ ℝ^d, the goal is to pick k centers C ⊆ ℝ^d that maximize the service ∑_{p∈P}φ(𝖽(p,C)) to the points P, where 𝖽(p,C) is the distance of p to its nearest center in C, and φ is a non-increasing service function φ: ℝ+ → ℝ+. This includes problems of placing k base stations as to maximize the total bandwidth to the clients - indeed, the closer the client is to its nearest base station, the more data it can send/receive, and the target is to place k base stations so that the total bandwidth is maximized. We provide an n^{ε^-O(d)} time algorithm for this problem that achieves a (1-ε)-approximation. Notably, the runtime does not depend on the parameter k and it works for an arbitrary non-increasing service function φ: ℝ+ → ℝ+. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arturs Backurs and Sariel Har-Peled 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.8 urn:nbn:de:0030-drops-122551 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode