Home Bookmarks Papers Blog

# Submodular Clustering in Low Dimensions

Arturs Backurs and Sariel Har-Peled.
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 $\PS \subseteq \Re^d$, the goal is to pick $k$ centers $\CS \subseteq \Re^d$ that maximize the service $\sum_{\pa \in \PS}\sFunc\bigl( \dSY{\pa}{\CS} \bigr)$ to the points $\PS$, where $\dSY{\pa}{\CS}$ is the distance of $\pa$ to its nearest center in $\CS$, and $\sFunc$ is a non-increasing service function $\sFunc : \Re^+ \to \Re^+$. 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^{\eps^{-O(d)}}$ time algorithm for this problem that achieves a $(1-\eps)$-approximation. Notably, the runtime does not depend on the parameter $k$ and it works for an arbitrary non-increasing service function $\sFunc : \Re^+ \to \Re^+$.
PDF : arXiv : DBLP.
Last modified: Sat 2022-07-23 20:24:05 UTC 2022 by Sariel Har-Peled