论文标题
追索权的力量：在线和动态模型中设施位置的更好算法
The Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Models
论文作者
论文摘要
在本文中，我们研究了在线的设施位置问题，该问题具有追索性和动态算法模型。在通过求助模型的在线上，客户逐一到达，我们的算法需要在所有时间步骤中维护良好的解决方案，只需对先前做出的决定（称为追索）进行一些更改。我们表明，经典的本地搜索技术可以导致$（1+ \ sqrt {2}+ε）$ - 仅使用$ o \ left的设施位置的竞争性在线算法（\ frac {\ frac {\ log n}ε\ log \ log \frac1ε\frac1ε\ \ right）$ amortized设施和客户端和客户求职。然后，我们转向问题的动态算法模型，其中主要目标是设计快速算法，这些算法在所有时间步骤中都保持良好的解决方案。我们表明，在线设施位置的结果以及Charikar and Guha [10]的随机本地搜索技术结合了$ O（1+ \ sqrt {2}+ε）$近似动态算法，并在增量设置中损坏了$ \ tilde o（n）$的amortized更新时间。请注意，运行时间几乎是最佳的，因为在一般度量空间中，指定新客户的位置需要$ω（n）$。我们算法的近似因素也与经典本地搜索算法的最佳离线分析相匹配。最后，我们研究了设施位置的完全动态模型，客户既可以到达又出发。我们的主要结果是该模型中的$ O（1）$ - 近似算法，$ O（| f |）$预处理时间和$ O（\ log^3 d）$用于HST度量空间的更新时间。 Using the seminal results of Bartal [4] and Fakcharoenphol, Rao and Talwar [17], which show that any arbitrary $N$-point metric space can be embedded into a distribution over HSTs such that the expected distortion is at most $O(\log N)$, we obtain a $O(\log |F|)$ approximation with preprocessing time of $O(|F|^2\log |F|)$和$ O（\ log^3 d）$摊销更新时间。
In this paper we study the facility location problem in the online with recourse and dynamic algorithm models. In the online with recourse model, clients arrive one by one and our algorithm needs to maintain good solutions at all time steps with only a few changes to the previously made decisions (called recourse). We show that the classic local search technique can lead to a $(1+\sqrt{2}+ε)$-competitive online algorithm for facility location with only $O\left(\frac{\log n}ε\log\frac1ε\right)$ amortized facility and client recourse. We then turn to the dynamic algorithm model for the problem, where the main goal is to design fast algorithms that maintain good solutions at all time steps. We show that the result for online facility location, combined with the randomized local search technique of Charikar and Guha [10], leads to an $O(1+\sqrt{2}+ε)$ approximation dynamic algorithm with amortized update time of $\tilde O(n)$ in the incremental setting. Notice that the running time is almost optimal, since in general metric space it takes $Ω(n)$ time to specify a new client's position. The approximation factor of our algorithm also matches the best offline analysis of the classic local search algorithm. Finally, we study the fully dynamic model for facility location, where clients can both arrive and depart. Our main result is an $O(1)$-approximation algorithm in this model with $O(|F|)$ preprocessing time and $O(\log^3 D)$ amortized update time for the HST metric spaces. Using the seminal results of Bartal [4] and Fakcharoenphol, Rao and Talwar [17], which show that any arbitrary $N$-point metric space can be embedded into a distribution over HSTs such that the expected distortion is at most $O(\log N)$, we obtain a $O(\log |F|)$ approximation with preprocessing time of $O(|F|^2\log |F|)$ and $O(\log^3 D)$ amortized update time.
