论文标题
完全动态的核心
Fully-Dynamic Coresets
论文作者
论文摘要
随着输入尺寸变得庞大，核心组（输入的小而代表性的摘要）比以往任何时候都更加相关。输入子集的加权集$ c_w $是$ \ varepsilon $ -coreset，如果任何可行解决方案$ s $相对于$ c_w $的成本在$ [1 {\ pm} \ varepsilon] $中，则与原始输入相对于原始输入。我们提供了一种非常通用的技术来计算完全动态的设置，可以添加或删除输入点。给定一个静态的$ \ varepsilon $ -coreset算法，该算法在时间$ t（n，\ varepsilon，λ）$中运行，并计算一个尺寸$ s（n，\ varepsilon，λ）$的核心，其中$ n $是输入点的数量，是$ 1 { - }λ$，我们给出了一个完全的概率，我们给出了一个完全范围的范围。 $ \ VAREPSILON $ -CORETET具有最差的更新时间$ o（（（\ log n）\ cdot t（s（n，\ varepsilon/\ log n，λ/n），\ varepsilon/\ log n，λ/n））$我们的技术是适用于仅插入设置的合并和还原技术的完全动态类似物。尽管我们的空间使用率为$ O（n）$，但我们在适应对手的存在下工作，并且我们表明当对手自适应时需要$ω（n）$空间。结果，我们将获得完全动态的$ \ varepsilon $ -coreset算法的$ k $ -Median和$ k $ -Means和$ k $ -Means，具有最差的更新时间$ O（\ varepsilon^{ - 2} k^2} k^2 \ log^5 n \ log^5 n \ log^3 k）$ o（ k）$忽略$ \ log \ log n $和$ \ log（1/\ varepsilon）$因子，并假设$ \ varepsilon，λ=ω（1/$ poly $（n））$。这些是$ k $ -Median和$ k $ -Means的第一个完全动态算法，具有最差的更新时间$ O（$ Poly $（k，\ log n，\ varepsilon^{ - 1}））$。我们还为任何完全动态的$（4-δ）$ - 近似算法提供了有条件的下限/查询时间，用于$ k $ -MEANS。
With input sizes becoming massive, coresets -- small yet representative summary of the input -- are relevant more than ever. A weighted set $C_w$ that is a subset of the input is an $\varepsilon$-coreset if the cost of any feasible solution $S$ with respect to $C_w$ is within $[1 {\pm} \varepsilon]$ of the cost of $S$ with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static $\varepsilon$-coreset algorithm that runs in time $t(n, \varepsilon, λ)$ and computes a coreset of size $s(n, \varepsilon, λ)$, where $n$ is the number of input points and $1 {-}λ$ is the success probability, we give a fully-dynamic algorithm that computes an $\varepsilon$-coreset with worst-case update time $O((\log n) \cdot t(s(n, \varepsilon/\log n, λ/n), \varepsilon/\log n, λ/n) )$ (this bound is stated informally), where the success probability is $1{-}λ$. Our technique is a fully-dynamic analog of the merge-and-reduce technique that applies to insertion-only setting. Although our space usage is $O(n)$, we work in the presence of an adaptive adversary, and we show that $Ω(n)$ space is required when adversary is adaptive. As a consequence, we get fully-dynamic $\varepsilon$-coreset algorithms for $k$-median and $k$-means with worst-case update time $O(\varepsilon^{-2}k^2\log^5 n \log^3 k)$ and coreset size $O(\varepsilon^{-2}k\log n \log^2 k)$ ignoring $\log \log n$ and $\log(1/\varepsilon)$ factors and assuming that $\varepsilon, λ= Ω(1/$poly$(n))$. These are the first fully-dynamic algorithms for $k$-median and $k$-means with worst-case update times $O($poly$(k, \log n, \varepsilon^{-1}))$. We also give conditional lower bound on update/query time for any fully-dynamic $(4 - δ)$-approximation algorithm for $k$-means.
