We provide nearly optimal algorithms for online facility location (OFL) with
predictions. In OFL, $n$ demand points arrive in order and the algorithm must
irrevocably assign each demand point to an open facility upon its arrival. The
objective is to minimize the total connection costs from demand points to
assigned facilities plus the facility opening cost. We further assume the
algorithm is additionally given for each demand point $x_i$ a natural
prediction $f_{x_i}^{\mathrm{pred}}$ which is supposed to be the facility
$f_{x_i}^{\mathrm{opt}}$ that serves $x_i$ in the offline optimal solution.
Our main result is an $O(\min\{\log {\frac{n\eta_\infty}{\mathrm{OPT}}},
\log{n} \})$-competitive algorithm where $\eta_\infty$ is the maximum
prediction error (i.e., the distance between $f_{x_i}^{\mathrm{pred}}$ and
$f_{x_i}^{\mathrm{opt}}$). Our algorithm overcomes the fundamental
$\Omega(\frac{\log n}{\log \log n})$ lower bound of OFL (without predictions)
when $\eta_\infty$ is small, and it still maintains $O(\log n)$ ratio even when
$\eta_\infty$ is unbounded. Furthermore, our theoretical analysis is supported
by empirical evaluations for the tradeoffs between $\eta_\infty$ and the
competitive ratio on various real datasets of different types.

我们提供了几乎最优算法，对具有预测固定需求点的在线设施位置问题进行求解，理论分析和实证评估均表明该算法在不同的位置预测误差下均能够维持较好的竞争比率。

在线设施位置问题及其预测

Online Facility Location with Predictions

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.

本文研究使用学习增强算法解决在线设施定位问题，在实际数据上验证该算法的性能并与当前最佳在线算法进行比较，结果表明该算法具有不错的竞争比率和适用性。

学习增强的在线设施选址

Learning Augmented Online Facility Location

Research on distributed machine learning algorithms has focused primarily on
one of two extremes - algorithms that obey strict concurrency constraints or
algorithms that obey few or no such constraints. We consider an intermediate
alternative in which algorithms optimistically assume that conflicts are
unlikely and if conflicts do arise a conflict-resolution protocol is invoked.
We view this "optimistic concurrency control" paradigm as particularly
appropriate for large-scale machine learning algorithms, particularly in the
unsupervised setting. We demonstrate our approach in three problem areas:
clustering, feature learning and online facility location. We evaluate our
methods via large-scale experiments in a cluster computing environment.

本文主要探讨分布式机器学习算法的一种中间情况 ——“乐观并发控制” 范式，并在聚类、特征学习和在线设施定位三个问题领域展示了其方法。通过集群计算环境中的大规模实验评估了我们的的算法。