Following the research agenda initiated by Munoz & Vassilvitskii [1] and Lykouris & Vassilvitskii [2] on learning-augmented online algorithms for classical online optimization problems, in this work, we consider the Online Facility Location problem under this framework. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and must be (irrevocably) assigned to an open facility upon arrival, without any knowledge about future demands. We present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities. We prove that the competitive ratio decreases smoothly from sublogarithmic in the number of demands to constant, as the error, i.e., the total distance of the predicted locations to the optimal facility locations, decreases towards zero. We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the error is optimal, up to constant factors. Finally, we evaluate our algorithm on real world data and compare our learning augmented approach with the current best online algorithm for the problem.
翻译:在本文中,我们沿着 Munoz & Vassilvitskii [1] 和 Lykouris & Vassilvitskii [2] 开始的研究议程,考虑了在线设施选址问题的学习增强在线算法框架。在在线设施选址问题中,需求以度量空间的形式逐个到达,并在到达时(不可撤销地)分配到一个开放设施,不知道未来需求的任何信息。我们提出了一种在线算法来解决在线设施选址问题,该算法利用了对最优设施位置的可能不完美的预测。我们证明,竞争比以对数次数与需求数量减少,当误差(即预测位置与最优设施位置的总距离)趋于零时,竞争比趋近于一个常数。我们还通过匹配下界来补充我们的分析,证明算法在错误上竞争比的依赖性是最优的(除了常数因子)。最后,我们在真实数据上评估了算法,并将我们的学习增强方法与该问题的当前最佳在线算法进行了比较。