$
\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.
Last modified: Sat 2022-07-23 20:24:05 UTC 2022 by Sariel Har-Peled