Home Bookmarks Papers Blog

# Submodular Clustering in Low Dimensions

$\newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\dSY}[2]{\Mh{\mathsf{d}}\pth{#1,#2}}% \newcommand{\sFunc}{\Mh{\mathsf{\varphi}}}% \newcommand{\Mh}[1]{#1} \newcommand{\CS}{\Mh{C}}% \newcommand{\pa}{\Mh{p}}% \newcommand{\pb}{\Mh{q}}% \newcommand{\pc}{\Mh{t}}% \newcommand{\PS}{P} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$
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.