论文标题
高效且稳定的完全动态设施位置
Efficient and Stable Fully Dynamic Facility Location
论文作者
论文摘要
我们考虑了完全动态的数据流中经典的设施位置问题，可以在其中插入和删除元素。在这个问题中，人们有兴趣在整个数据流中维护稳定，高质量的解决方案，而每次更新仅需很少的时间（插入或删除）。我们研究了该问题，并提供了第一种算法，同时每次更新都保持恒定的近似值并产生多毛的摊销。我们通过实验分析来补充我们的理论结果，以显示我们方法的实际效率。
We consider the classic facility location problem in fully dynamic data streams, where elements can be both inserted and deleted. In this problem, one is interested in maintaining a stable and high quality solution throughout the data stream while using only little time per update (insertion or deletion). We study the problem and provide the first algorithm that at the same time maintains a constant approximation and incurs polylogarithmic amortized recourse per update. We complement our theoretical results with an experimental analysis showing the practical efficiency of our method.
