论文标题
低维
Submodular Clustering in Low Dimensions
论文作者
论文摘要
我们研究了一个聚类问题，其目标是将输入点的覆盖率最大化，以$ k $选择的中心。具体而言，给定一组$ n $点$ p \ subseteq \ mathbb {r}^d $，目标是选择$ k $中心$ c \ subseteq \ subseteq \ mathbb {r}^d $，最大化服务$ \ sum_ sum_ {p \ in p} \ mathsf或big big big bim y math y sum_点$ p $，其中$ \ mathsf {d}（p，c）$是$ p $ $ p $与$ c $的最近中心的距离，而$ \mathsfφ$是一种非increasing服务功能$ \mathsfφ：\ mathbb {r}这包括放置$ k $基站的问题，以最大程度地提高客户的总带宽 - 实际上，客户端越接近其最近的基站，它可以发送/接收的数据越多，并且目标是放置$ k $ base站，以便最大化总的base子。我们为此问题提供了一个$ n^{\ varepsilon^{ - o（d）}} $ time算法，以实现$（1- \ varepsilon）$ - 近似。值得注意的是，运行时不取决于参数$ k $，并且它适用于任意非侵扰服务功能$ \MATHSFφ：\ MATHBB {r}^+ \ to \ Mathbb {r}^+ $。
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 \subseteq \mathbb{R}^d$, the goal is to pick $k$ centers $C \subseteq \mathbb{R}^d$ that maximize the service $ \sum_{p \in P}\mathsfφ\bigl( \mathsf{d}(p,C) \bigr) $ to the points $P$, where $\mathsf{d}(p,C)$ is the distance of $p$ to its nearest center in $C$, and $\mathsfφ$ is a non-increasing service function $\mathsfφ : \mathbb{R}^+ \to \mathbb{R}^+$. 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^{\varepsilon^{-O(d)}}$ time algorithm for this problem that achieves a $(1-\varepsilon)$-approximation. Notably, the runtime does not depend on the parameter $k$ and it works for an arbitrary non-increasing service function $\mathsfφ : \mathbb{R}^+ \to \mathbb{R}^+$.
