论文标题
通过已知的删除顺序（例如滑动窗口）的完全动态到灌输量减少
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
论文作者
论文摘要
动态算法有三种主要口味：$ \ mathit {cormemental} $（仅插入），$ \ mathit {distemental} $（仅删除）或$ \ mathit {fullation {full} $ $ \ $ \ mathit {dynamit {dynamit {dynamitions} $（两个插入和删除）。完全动态的是动态算法设计的圣杯；显然，这比其他两个更一般，但是严格困难吗？几项作品通过利用渐进/减少算法的任何特定结构来减少动态或减少模型（例如[HK99，HLT01，BKS12，ADKKP16，BS80，BS80，BS80，OL81，OVL81，OVL81]），或DELETIONS/DELETIONS/knk.144.g. [aw.aw.aw aw.aw.aw.我们在这项工作中的目标是获得尽可能笼统的黑盒全部减少。我们发现需要以下条件： $ \ bullet $增量算法必须具有最差的案例（而不是摊销）运行时间保证。 $ \ bullet $减少必须在我们所谓的$ \ mathit {删除} $ - $ \ mathit {look} $ - $ \ mathit {tark} $ $ $ \ mathit {modelit {model {model {model {model} $中，事先知道当前元素之间的删除顺序。一个显着的实际示例是“滑动窗口”（FIFO）更新顺序。 在这些条件下，我们设计： $ \ bullet $是一种简单，实用，摊销的，最糟糕的动态至最差的销售减少，$ \ log（t）$（t）$ - 因子 - 因子开销，其中$ t $是$ t $是更新的总数。 $ \ bullet $理论上最糟糕的案例，以$ \ mathsf {polylog}（t）$ - 因子$ - 因子 - 因子 - 因子 - 因子 - 因子在运行时的开销。
Dynamic algorithms come in three main flavors: $\mathit{incremental}$ (insertions-only), $\mathit{decremental}$ (deletions-only), or $\mathit{fully}$ $\mathit{dynamic}$ (both insertions and deletions). Fully dynamic is the holy grail of dynamic algorithm design; it is obviously more general than the other two, but is it strictly harder? Several works managed to reduce fully dynamic to the incremental or decremental models by taking advantage of either specific structure of the incremental/decremental algorithms (e.g. [HK99, HLT01, BKS12, ADKKP16, BS80, OL81, OvL81]), or specific order of insertions/deletions (e.g. [AW14,HKNS15,KPP16]). Our goal in this work is to get a black-box fully-to-incremental reduction that is as general as possible. We find that the following conditions are necessary: $\bullet$ The incremental algorithm must have a worst-case (rather than amortized) running time guarantee. $\bullet$ The reduction must work in what we call the $\mathit{deletions}$-$\mathit{look}$-$\mathit{ahead}$ $\mathit{model}$, where the order of deletions among current elements is known in advance. A notable practical example is the "sliding window" (FIFO) order of updates. Under those conditions, we design: $\bullet$ A simple, practical, amortized-fully-dynamic to worst-case-incremental reduction with a $\log(T)$-factor overhead on the running time, where $T$ is the total number of updates. $\bullet$ A theoretical worst-case-fully-dynamic to worst-case-incremental reduction with a $\mathsf{polylog}(T)$-factor overhead on the running time.
