论文标题
在滑动窗口上计算欧几里得k-Center
Computing Euclidean k-Center over Sliding Windows
论文作者
论文摘要
在滑动窗口模型中的欧几里得$ k $中心问题中，数据流中给出了输入点，目标是找到$ k $最小的一致球，其工会涵盖了该流的最新点。在此模型中，只允许检查一次输入点，并且可以用于存储相对信息的空间量受到限制。 Cohen-Addad等人cohen-addad et al。在本文中，我们提出了使用O（$ 1/ε\logα$）点的Euclidean $ 1 $中心问题的$（3+ε）$ - 近似算法。我们提出了一种欧几里得$ k $中心问题的算法，该算法维持尺寸$ o（k）$的核心。我们的算法给出了$（C + 2 \ SQRT {3} +ε）$ - 使用O（$ K/ε\logα$）点的Euclidean $ k $中心问题通过使用任何给定的$ C $ -C $ -C $ - APPROXIMATION，其中$ C $是$ C $是一个正真实的实际数字。例如，通过使用$ 2 $ -Approximation〜 \ cite {Feder-Greene-1988}，我们的算法给出了$（2 + 2 \ 2 \ 2 \ sqrt {3} +ε）$ - 近似值（$ \ of 5.465 $），使用$ o（k \ log log k）$ time。这是Cohen-Addad等人的近似值（6+ε）$的近似因素的改进。此外，我们删除了$α$的假设。我们的想法可以适应公制直径问题和度量$ k $中心问题以消除假设。对于低维欧几里得空间，我们提供了一种近似算法，可以保证更好的近似值。
In the Euclidean $k$-center problem in sliding window model, input points are given in a data stream and the goal is to find the $k$ smallest congruent balls whose union covers the $N$ most recent points of the stream. In this model, input points are allowed to be examined only once and the amount of space that can be used to store relative information is limited. Cohen-Addad et al.~\cite{cohen-2016} gave a $(6+ε)$-approximation for the metric $k$-center problem using O($k/ε\log α$) points, where $α$ is the ratio of the largest and smallest distance and is assumed to be known in advance. In this paper, we present a $(3+ε)$-approximation algorithm for the Euclidean $1$-center problem using O($1/ε\log α$) points. We present an algorithm for the Euclidean $k$-center problem that maintains a coreset of size $O(k)$. Our algorithm gives a $(c+2\sqrt{3} + ε)$-approximation for the Euclidean $k$-center problem using O($k/ε\log α$) points by using any given $c$-approximation for the coreset where $c$ is a positive real number. For example, by using the $2$-approximation~\cite{feder-greene-1988} of the coreset, our algorithm gives a $(2+2\sqrt{3} + ε)$-approximation ($\approx 5.465$) using $O(k\log k)$ time. This is an improvement over the approximation factor of $(6+ε)$ by Cohen-Addad et al.~\cite{cohen-2016} with the same space complexity and smaller update time per point. Moreover we remove the assumption that $α$ is known in advance. Our idea can be adapted to the metric diameter problem and the metric $k$-center problem to remove the assumption. For low dimensional Euclidean space, we give an approximation algorithm that guarantees an even better approximation.
