# Online Facility Location with Predictions

Shaofeng H.-C. Jiang
Peking University
Email<EMAIL_ADDRESS>
&Erzhi Liu
Shanghai Jiao Tong University
Email<EMAIL_ADDRESS>
&You Lyu
Shanghai Jiao Tong University
Email<EMAIL_ADDRESS>
&Zhihao Gavin Tang
Shanghai University of Finance and Economics
Email<EMAIL_ADDRESS>
&Yubo Zhang
Peking University
Email<EMAIL_ADDRESS>

###### Abstract

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}}{\operatorname{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.

##  1 Introduction

We study the online facility location (OFL) problem with predictions. In OFL,
given a metric space $(\mathcal{X},d)$, a ground set
$\mathcal{D}\subseteq\mathcal{X}$ of demand points, a ground set
$\mathcal{F}\subseteq\mathcal{X}$ of facilities, and an _opening cost_
function $w:\mathcal{F}\to\mathbb{R}_{+}$, the input is a sequence of demand
points $X:=(x_{1},\ldots,x_{n})\subseteq\mathcal{D}$, and the online algorithm
must _irrevocably_ assign $x_{i}$ to some _open_ facility, denoted as $f_{i}$,
upon its arrival, and an open facility cannot be closed. The goal is to
minimize the following objective

$\displaystyle\sum_{f\in F}{w(f)}+\sum_{x_{i}\in X}{d(x_{i},f_{i})},$

where $F$ is the set of open facilities.

Facility location is a fundamental problem in both computer science and
operations research, and it has been applied to various domains such as supply
chain management (Melo et al., 2009), distribution system design (Klose &
Drexl, 2005), healthcare (Ahmadi-Javid et al., 2017), and more applications
can be found in surveys (Drezner & Hamacher, 2002; Laporte et al., 2019). Its
online variant, OFL, was also extensively studied and well understood. The
state of the art is an $O(\frac{\log n}{\log\log n})$-competitive
deterministic algorithm proposed by Fotakis (2008), and the same work shows
this ratio is tight.

We explore whether or not the presence of certain natural predictions could
help to bypass the $O(\frac{\log n}{\log\log n})$ barrier. Specifically, we
consider the setting where each demand point $x_{i}$ receives a predicted
facility $f_{x_{i}}^{\mathrm{pred}}$ that is supposed to be $x_{i}$’s assigned
facility in the (offline) optimal solution. This prediction is very natural,
and it could often be easily obtained in practice. For instance, if the
dataset is generated from a latent distribution, then predictions may be
obtained by analyzing past data. Moreover, predictions could also be obtained
from external sources, such as expert advice, and additional features that
define correlations among demand points and/or facilities. Previously,
predictions of a similar flavor were also considered for other online
problems, such as online caching (Rohatgi, 2020; Lykouris & Vassilvitskii,
2021), ski rental (Purohit et al., 2018; Gollapudi & Panigrahi, 2019) and
online revenue maximization (Medina & Vassilvitskii, 2017).

###  1.1 Our Results

Our main result is a near-optimal online algorithm that offers a smooth
tradeoff between the prediction error and the competitive ratio. In
particular, our algorithm is $O(1)$-competitive when the predictions are
perfectly accurate, i.e., $f_{x_{i}}^{\mathrm{pred}}$ is the nearest neighbor
of $x_{i}$ in the optimal solution for every $1\leq i\leq n$. On the other
hand, even when the predictions are completely wrong, our algorithm still
remains $O(\log n)$-competitive. As in the literature of online algorithms
with predictions, our algorithm does not rely on the knowledge of the
prediction error $\eta_{\infty}$.

######  Theorem 1.1.

There exists an
$O(\min\\{\log{n},\max\\{1,\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}}\\}\\})$-competitive
algorithm for the OFL with predictions, where $\eta_{\infty}:=\max_{1\leq
i\leq n}{d(f_{x_{i}}^{\mathrm{pred}},f_{x_{i}}^{\mathrm{opt}})}$ measures the
maximum prediction error, and $f_{x_{i}}^{\mathrm{opt}}$ is the nearest
neighbor of $x_{i}$ from the offline optimal solution
$\operatorname{OPT}$111When the context is clear, we also use
$\operatorname{OPT}$ to denote the optimal solution..

Indeed, we can also interpret our result under the robustness-consistency
framework which is widely considered in the literature of online algorithms
with predictions (cf. Lykouris & Vassilvitskii (2021)), where the robustness
and consistency stand for the competitive ratios of the algorithm in the cases
of arbitrarily bad predictions and perfect predictions, respectively. Under
this language, our algorithm is $O(1)$-consistent and $O(\log n)$-robust. We
also remark that our robustness bound nearly matches the lower bound for the
OFL without predictions.

One might wonder whether or not it makes sense to consider a related error
measure,
$\eta_{1}:=\sum_{i=1}^{n}{d(f_{x_{i}}^{\mathrm{pred}},f_{x_{i}}^{\mathrm{opt}})}$,
which is the _total_ error of predictions. Our lower bound result (Theorem
1.2) shows that a small $\eta_{1}$ is not helpful, and the dependence of
$\eta_{\infty}$ in our upper bound is fundamental (see Section 4 for a more
detailed explanation). The lower bound also asserts that our algorithm is
nearly tight in the dependence of $\eta_{\infty}$.

######  Theorem 1.2.

Consider OFL with predictions with a uniform opening cost of $1$. For every
$\eta_{\infty}\in(0,1]$, there exists a class of inputs, such that no
(randomized) online algorithm is
$o(\frac{\log\frac{n\eta_{\infty}}{\operatorname{OPT}}}{\log\log
n})$-competitive, even when $\eta_{1}=O(1)$.

As suggested by an anonymous reviewer, it might be possible to make the error
measure $\eta_{\infty}$ more “robust” by taking “outliers” into account. A
more detailed discussion on this can be found in Section A.

##### Empirical evaluation.

We simulate our algorithm on both Euclidean and graph (shortest-path)
datasets, and we measure the tradeoff between $\eta_{\infty}$ and the
empirical competitive ratio, by generating random predictions whose
$\eta_{\infty}$ is controlled to be around some target value. We compare with
two baselines, the $O(\log n)$-competitive algorithm by Meyerson (2001) which
do not use the prediction at all, and a naive algorithm that always trusts the
prediction. Our algorithm significantly outperforms Meyerson’s algorithm when
$\eta_{\infty}\to 0$, and is still comparable to Meyerson’s algorithm when
$\eta_{\infty}$ is large where the follow-prediction baseline suffers a huge
error.

We observe that our lead is even more significant on datasets with non-uniform
opening cost, and this suggests that the prediction could be very useful in
the non-uniform setting. This phenomenon seems to be counter-intuitive since
the error guarantee $\eta_{\infty}$ only concerns the connection costs without
taking the opening cost into consideration (i.e., it could be that a small
$\eta_{\infty}$ is achieved by predictions of huge opening cost), which seems
to mean the prediction may be less useful. Therefore, this actually
demonstrates the superior capability of our algorithm in using the limited
information from the predictions even in the non-uniform opening cost setting.

Finally, we test our algorithm along with a very simple predictor that does
not use any sophisticated ML techniques or specific features of the dataset,
and it turns out that such a simple predictor already achieves a reasonable
performance. This suggests that more carefully engineered predictors in
practice is likely to perform even better, and this also justifies our
assumption of the existence of a good predictor.

##### Comparison to independent work.

A recent independent work by Fotakis et al. (2021a) considers OFL with
predictions in a similar setting. We highlight the key differences as follows.

(i) We allow arbitrary opening cost $w(\cdot)$, while Fotakis et al. (2021a)
only solves the special case of _uniform_ facility location where all opening
costs are equal. This is a significant difference, since as we mentioned (and
will discuss in Section 1.2)), the non-uniform opening cost setting introduces
outstanding technical challenges that require novel algorithmic ideas.

(ii) For the uniform facility location setting, our competitive ratio is
$O(\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}})=O(\log{\frac{n\eta_{\infty}}{w}})$,
while the ratio in Fotakis et al. (2021a) is
$\frac{\log(\text{err}_{0})}{\log(\text{err}_{1}^{-1}\log(\text{err}_{0}))}$,
where $\text{err}_{0}=n\eta_{\infty}/w$, $\text{err}_{1}=\eta_{1}/w$ and $w$
is the uniform opening cost. Our ratio is comparable to theirs when $\eta_{1}$
is relatively small. However, theirs seems to be better when $\eta_{1}$ is
large, and in particular, it was claimed in Fotakis et al. (2021a) that the
ratio becomes constant when $\text{err}_{1}\approx\text{err}_{0}$.
Unfortunately, we think this claim contradicts with our lower bound (Theorem
1.2) which essentially asserts that $\eta_{1}=O(\eta_{\infty})$ is not helpful
for the ratio. Moreover, when $\eta_{1}$ is large, we find their ratio is
actually not well-defined since the denominator
$\log(\text{err}_{1}^{-1}\log(\text{err}_{0}))$ is negative. Therefore, we
believe there might be some unstated technical assumptions, or there are
technical issues remaining to be fixed, when $\eta_{1}$ is large.

Another independent work by Panconesi et al. (2021) considers a different
model of predictions which is not directly comparable to ours. Before the
arrival of the first demand point, $k$ sets
$\mathcal{S}_{1},\mathcal{S}_{2},\ldots,\mathcal{S}_{k}\subseteq\mathcal{F}$
are provided as multiple machine-learned advice, each suggesting a list of
facilities to be opened. Their algorithm only uses facilities in
$\mathcal{S}=\bigcup_{i}\mathcal{S}_{i}$ and achieves a cost of
$O(\log(|\mathcal{S}|)\operatorname{OPT}(\mathcal{S}))$ where
$\operatorname{OPT}(\mathcal{S})$ is the optimal using only facilities in
$\mathcal{S}$, and the algorithm also has a worst-case ratio of $O(\frac{\log
n}{\log\log n})$ in case the predictions are inaccurate. Similar to the
abovementioned Fotakis et al. (2021a) result, this result only works for
uniform opening cost while ours works for arbitrary opening costs.

###  1.2 Technical Overview

Since we aim for a worst-case (i.e., when the predictions are inaccurate)
$O(\log n)$ ratio, our algorithm is based on an $O(\log n)$-competitive
algorithm (that does not use predictions) by Meyerson (2001), and we design a
new procedure to make use of predictions. In particular, upon the arrival of
each demand point, our algorithm first runs the steps of Meyerson’s algorithm
, which we call the Meyerson step, and then runs a new procedure (proposed in
this paper) to open additional facilities that are “near” the prediction,
which we call the Prediction step.

We make use of the following crucial property of Meyerson’s algorithm. Suppose
before the first demand point arrives, the algorithm is already provided with
an initial facility set $\bar{F}$, such that for every facility $f^{*}$ opened
in $\operatorname{OPT}$, $\bar{F}$ contains a facility $f^{\prime}$ that is of
distance $\eta_{\infty}$ to $f^{*}$, then Meyerson’s algorithm is
$O(\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}})$-competitive. To this end,
our Prediction step aims to open additional facilities so that for each
facility in $\operatorname{OPT}$, the algorithm would soon open a close enough
facility.

##### Uniform opening cost.

There is a simple strategy that achieves this goal for the case of _uniform
opening cost_. Whenever the Meyerson step decides to open a facility, we
further open a facility at the predicted location. By doing so, we would pay
twice as the Meyerson algorithm does in order to open the extra facility. As a
reward, when the prediction error $\eta_{\infty}$ is small, the extra facility
would be good and close enough to the optimal facility.

##### Non-uniform opening cost.

Unfortunately, this strategy does not extend to the non-uniform case.
Specifically, opening a facility exactly at the predicted location could be
prohibitively expensive as it may have huge opening cost. Instead, one needs
to open a facility that is “close” to the prediction, but attention must be
paid to the tradeoff between the opening cost and the proximity to the
prediction.

The design of the Prediction step for the non-uniform case is the most
technical and challenging of our paper. We start with opening an initial
facility that is far from the prediction, and then we open a series of
facilities within balls (centered at the prediction) of geometrically
decreasing radius, while we also allow the opening cost of the newly open
facility to be doubled each time. We stop opening facilities if the total
opening cost exceeds the cost incurred by the preceding Meyerson step, in
order to have the opening cost bounded.

We show that our procedure always opens a “correct” facility $\hat{f}$ that is
$\Theta(\eta_{\infty})$ apart to the corresponding facility in
$\operatorname{OPT}$, and that the total cost until $\hat{f}$ is opened is
merely $O(\operatorname{OPT})$. This is guaranteed by the gradually decreasing
ball radius when we build additional facilities (so that the “correct”
facility will not be skipped), and that the total opening cost could be
bounded by that of the last opened facility (because of the doubling opening
cost). Once we open this $\hat{f}$, subsequent runs of Meyerson steps would be
$O(\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}})$-competitive.

###  1.3 Related Work

OFL is introduced by Meyerson (2001), where a randomized algorithm that
achieves competitive ratios of $O(1)$ and $O(\log{n})$ are obtained in the
setting of random arrival order and adversarial arrival order, respectively.
Later, Fotakis (2008) gave a lower bound of
$\Omega(\frac{\log{n}}{\log{\log{n}}})$ and proposed a deterministic algorithm
matching the lower bound. In the same paper, Fotakis also claimed that an
improved analysis of Meyerson’s algorithm actually yields an
$O(\frac{\log{n}}{\log{\log{n}}})$ competitive ratio in the setting of
adversarial order. Apart from this classical OFL, other variants of it are
studied as well. Divéki & Imreh (2011) and Bamas et al. (2020b) considered the
dynamic variant, in which an open facility can be reassigned. Another variant,
OFL with evolving metrics, was studied by Eisenstat et al. (2014) and Fotakis
et al. (2021b).

There is a recent trend of studying online algorithms with predictions and
many classical online problems have been revisited in this framework. Lykouris
& Vassilvitskii (2021) considered online caching problem with predictions and
gave a formal definition of consistency and robustness. For the ski-rental
problem, Purohit et al. (2018) gave an algorithm with a hyper parameter to
maintain the balance of consistency and robustness. They also considered non-
clairvoyant scheduling on a single machine. Gollapudi & Panigrahi (2019)
designed an algorithm using multiple predictors to achieve low prediction
error. Recently, Wei & Zhang (2020) showed a tight robustness-consistency
tradeoff for the ski-rental problem. For the caching problem, Lykouris &
Vassilvitskii (2021) adapted Marker algorithm to use predictions. Following
this work, Rohatgi (2020) provided an improved algorithm that performs better
when the predictor is misleading. Bamas et al. (2020b) extended the online
primal-dual framework to incorporate predictions and applied their framework
to solve the online covering problem. Medina & Vassilvitskii (2017) considered
the online revenue maximization problem and Bamas et al. (2020a) studied the
online speed scaling problem. Both Antoniadis et al. (2020) and Dütting et al.
(2021) considered the secretary problems with predictions. Jiang et al. (2021)
studied online matching problems with predictions in the constrained adversary
framework. Azar et al. (2021) and Lattanzi et al. (2020) considered flow time
scheduling and online load balancing, respectively, in settings with error-
prone predictions.

##  2 Preliminaries

Recall that we assume a underlying metric space $(\mathcal{X},d)$. For
$S\subseteq\mathcal{X},x\in\mathcal{X}$, define $d(x,S):=\min_{y\in
S}{d(x,y)}$. For an integer $t$, let $[t]:=\\{1,2,\ldots,t\\}$. We normalize
the opening cost function $w$ so that the minimum opening cost equals $1$, and
we round down the opening cost of each facility to the closest power of $2$.
This only increases the ratio by a factor of $2$ which we can afford (since we
make no attempt to optimize the constant hidden in big $O$). Hence, we assume
the domain of $w$ is $\\{2^{i-1}\mid i\in[L]\\}$ for some $L$. Further, we use
$G_{k}$ to denote the set of facilities whose opening cost is at most
$2^{k-1}$, i.e. $G_{k}:=\\{f\in\mathcal{F}\mid w(f)\leq 2^{k-1}\\},\forall
1\leq k\leq L$. Observe that $G_{0}=\emptyset$.

##  3 Our Algorithm: Prediction-augmented Meyerson

We prove Theorem 1.1 in this section. Our algorithm, stated in Algorithm 1,
consists of two steps, the Meyerson step and the Prediction step. Upon the
arrival of each demand point $x$, we first run the Meyerson algorithm Meyerson
(2001), and let $\operatorname{cost}_{\mathrm{M}}(x)$ be the cost from the
Meyerson step. Roughly, for a demand point $x$, the Meyerson algorithm first
finds for each $k\geq 1$, a facility $f_{k}$ which is the nearest to $x$,
among facilities of opening cost at most $2^{k-1}$ and those have been opened,
and let $\delta_{k}=d(x,f_{k})$. Then, open a random facility from
$\\{f_{k}\\}_{k}$, such that $f_{k}$ is picked with probability
$(\delta_{k-1}-\delta_{k})/2^{k}$. For technical reasons, we do not normalize
$\sum_{k}{p_{k}}$, and we simply truncate if $\sum_{k}{p_{k}}>1$. Next, we
pass the cost incurred in the Meyerson step (which is random) as the budget
$q$ to the Prediction step, and the Prediction step would use this budget to
open a series of facilities through the repeat-until loop. Specifically, for
each iteration in this loop, a facility is to be opened around distance $r$ to
the prediction, where $r$ is geometrically decreasing, and the exact facility
is picked to be the one with the minimum opening cost. The ratio of this
algorithm is stated as follows.

Algorithm 1 Prediction-augmented Meyerson

1:initialize $F\leftarrow\emptyset$, $F_{\mathrm{P}}\leftarrow\emptyset$
$\triangleright$ $F,F_{\textsc{P}}$ are the set of all open facilities and
those opened by Pred

2:for arriving demand point $x\in X$ and its associated
$f_{x}^{\mathrm{pred}}$ do

3: $\operatorname{cost}_{\mathrm{M}}(x)\leftarrow\textsc{Mey}\left(x\right)$

4:
$\textsc{Pred}\left(f_{x}^{\mathrm{pred}},\operatorname{cost}_{\mathrm{M}}(x)\right)$

5:procedure Mey($x$)

6: for $k\in[L]$ do

7: $f_{k}\leftarrow\arg\min_{f\in F\cup G_{k}}d(x,f)$

8: $\delta_{k}\leftarrow d(x,f_{k})$

9: $p_{k}\leftarrow(\delta_{k-1}-\delta_{k})/2^{k}$, where $\delta_{0}=d(x,F)$

10: let $s_{k}\leftarrow\sum_{i=k}^{L}p_{i}$ for $k\in[L]$

11: sample $r\sim\text{Uni}[0,1]$, and let $i\in[L]$ be the index such that
$r\in[s_{i+1},s_{i})$

12: if such $i$ exists then

13: $F\leftarrow F\cup f_{i}$ $\triangleright$ open facility at $f_{i}$

14: connect $x$ to the nearest neighbor in $F$

15: return $d(x,F)+w(f_{i})$ $\triangleright$ if $i$ does not exist, simply
return $d(x,F)$

16:procedure Pred($f_{x}^{\mathrm{pred}},q$)

17: repeat

18: $r\leftarrow\frac{1}{2}d(f_{x}^{\mathrm{pred}},F_{\mathrm{P}})$

19: $f_{\mathrm{open}}\leftarrow\arg\min_{f:d(f_{x}^{\mathrm{pred}},f)\leq
r}w(f)$ $\triangleright$ break ties by picking the closest facility to
$f_{x}^{\mathrm{pred}}$

20: if $q\geq w(f_{\mathrm{open}})$ then

21: $F\leftarrow F\cup f_{\mathrm{open}}$, $F_{\mathrm{P}}\leftarrow
F_{\mathrm{P}}\cup f_{\mathrm{open}}$ $\triangleright$ open facility at
$f_{\mathrm{open}}$

22: $q\leftarrow q-w(f_{\mathrm{open}})$

23: until $q<w(f_{\mathrm{open}})$

24: open facility at $f_{\mathrm{open}}$ with probability
$\frac{q}{w(f_{\mathrm{open}})}$, and update $F,F_{\mathrm{P}}$

######  Theorem 3.1.

Prediction-augmented Meyerson is
$O(\min\\{\log{n},\max\\{1,\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}}\\}\\})$-competitive.

##### Calibrating predictions.

Recall that
$\eta_{\infty}=\max_{i\in[n]}{d(f_{x_{i}}^{\mathrm{pred}},f_{x_{i}}^{\mathrm{opt}})}$
can be unbounded. We show how to “calibrate” the bad predictions so that
$\eta_{\infty}=O(\operatorname{OPT})$. Specifically, when a demand point $x$
arrives, we compute
$f^{\prime}_{x}:=\arg\min_{f\in\mathcal{F}}\\{d(x,f)+w(f)\\}$, and we
calibrate $f_{x}^{\mathrm{pred}}$ by letting
$f_{x}^{\mathrm{pred}}=f^{\prime}_{x}$ if $d(x,f_{x}^{\mathrm{pred}})\geq
2d(x,f^{\prime}_{x})+w(f^{\prime}_{x})$.

We show the calibrated predictions satisfy
$\eta_{\infty}=O(\operatorname{OPT})$. Indeed, for every demand point $x$,
$d(f^{\prime}_{x},f_{x}^{\mathrm{opt}})\leq
d(x,f^{\prime}_{x})+d(x,f_{x}^{\mathrm{opt}})\leq
2d(x,f^{\prime}_{x})+w(f^{\prime}_{x})\leq O(\operatorname{OPT})$, where the
second to last inequality follows from the optimality (i.e., the connection
cost $d(x,f_{x}^{\mathrm{opt}})$ has to be smaller than the cost of first
opening $f^{\prime}_{x}$ then connecting $x$ to $f^{\prime}_{x}$). Note that,
if $\eta_{\infty}=O(\operatorname{OPT})$ then
$\frac{n\eta_{\infty}}{\operatorname{OPT}}=O(n)$, hence it suffices to prove a
single bound $O(\max\\{1,\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}}\\})$
for Theorem 3.1 (i.e., ignoring the outer $\min$).

##### Algorithm analysis.

Let $F_{\operatorname{opt}}$ be the set of open facilities in the optimal
solution. We examine each $f^{*}\in F_{\operatorname{opt}}$ and its
corresponding demand points separately, i.e. those demand points connecting to
$f^{*}$ in the optimal solution. We denote this set of demand points by
$X(f^{*})$.

######  Definition 3.2 (Open facilities).

For every demand point $x$, let $F(x)$ be the set of open facilities right
after the arrival of request $x$, $\bar{F}(x)$ be the set of open facilities
right before the arrival of $x$, and $\hat{F}(x)=F(x)\setminus\bar{F}(x)$ be
the set of the newly-open facilities on the arrival of $x$. Moreover, let
$F_{\mathrm{M}}(x),F_{\mathrm{P}}(x)$ be a partition of $F(x)$, corresponding
to the facilities opened by Mey and Pred, respectively. Let
$\bar{F}_{\mathrm{M}}(x),\hat{F}_{\mathrm{M}}(x),\bar{F}_{\mathrm{P}}(x),\hat{F}_{\mathrm{P}}(x)$
be defined similarly.

######  Definition 3.3 (Costs).

Let
$\operatorname{cost}_{\mathrm{M}}(x)=w(\hat{F}_{\mathrm{M}}(x))+d\left(x,\left(F_{\mathrm{M}}(x)\cup\bar{F}_{\mathrm{P}}(x)\right)\right)$
be the the total cost from Mey step. Let
$\operatorname{cost}_{\mathrm{P}}(x)=w(\hat{F}_{\mathrm{P}}(x))$ be the cost
from Pred step. Let
$\operatorname{cost}(x)=\operatorname{cost}_{\mathrm{M}}(x)+\operatorname{cost}_{\mathrm{P}}(x)$
be the total cost of $x$.

Recall that after the Mey step, we assign a total budget of
$\operatorname{cost}_{\mathrm{M}}(x)$ to the Pred step. That is, the expected
cost from the Pred step is upper bounded by the cost from the Mey step. We
formalize this intuition in the following lemma.

######  Lemma 3.4.

For each demand point $x\in X$,
$\operatorname{\mathbb{E}}[\operatorname{cost}(x)]=2\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x)]$.

###### Proof.

Consider the expected cost from the Pred step. Given arbitrary $F_{p},q$,
there is only one random event from the algorithm and it is straightforward to
see that the expected cost equals $q$. Notice that our algorithm assigns a
total budget of $q=\operatorname{cost}_{\mathrm{M}}(x)$. Thus,
$\operatorname{\mathbb{E}}[\operatorname{cost}(x)]=\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x)+\operatorname{cost}_{\mathrm{P}}(x)]=2\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x)]$.
∎

Therefore, we are left to analyze the total expected cost from the Mey step.
The following lemma is the most crucial to our analysis. Before continuing to
the proof of the lemma, we explain how it concludes the proof of our main
theorem.

######  Lemma 3.5.

For every facility $f^{*}\in F_{\operatorname{opt}}$, we have

$\sum_{x\in
X(f^{*})}\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x)]\leq
O\left(\max\left\\{1,\log\frac{n\eta_{\infty}}{\operatorname{OPT}}\right\\}\right)\cdot\left(w(f^{*})+\sum_{x\in
X(f^{*})}d(x,f^{*})\right)+O\left(\frac{|X(f^{*})|}{n}\cdot\operatorname{OPT}\right).$

##### Proof of Theorem 3.1.

Summing up the equation of Lemma 3.5 for every $f^{*}\in
F_{\operatorname{opt}}$, we have

$\displaystyle\operatorname{\mathbb{E}}[\operatorname{ALG}]$
$\displaystyle=\sum_{x\in
X}\operatorname{\mathbb{E}}[\operatorname{cost}(x)]=2\sum_{x\in
X}\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x)]=2\sum_{f^{*}\in
F_{\operatorname{opt}}}\sum_{x\in
X(f^{*})}\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x)]$
$\displaystyle\leq\sum_{f^{*}\in
F_{\operatorname{opt}}}\left(O\left(\max\left\\{1,\log\frac{n\eta_{\infty}}{\operatorname{OPT}}\right\\}\right)\cdot\left(w(f^{*})+\sum_{x\in
X(f^{*})}d(x,f^{*})\right)+O\left(\frac{|X(f^{*})|}{n}\cdot\operatorname{OPT}\right)\right)$
$\displaystyle=O\left(\max\left\\{1,\log\frac{n\eta_{\infty}}{\operatorname{OPT}}\right\\}\right)\cdot\operatorname{OPT},$

where the second equality is by Lemma 3.4 and the inequality is by Lemma 3.5,
and this also implies that the ratio is $O(1)$ when $\eta_{\infty}=0$. ∎

###  3.1 Proof of Lemma 3.5

Fix an arbitrary $f^{*}\in F_{\operatorname{opt}}$. Let $\ell^{*}$ be the
integer such that $w(f^{*})=2^{\ell^{*}-1}$, or equivalently $f^{*}\in
G_{\ell^{*}}$. Let $X(f^{*})=\\{x_{1},x_{2},\ldots,x_{m}\\}$ be listed
according to their arrival order. We remark that there can be other demand
points arriving between $x_{i}$ and $x_{i+1}$, but they must be connected to
other facilities in the optimal solution. Let $\ell_{i}$ be the index $\ell$
such that $d(f^{*},\bar{F}(x_{i}))\in[2^{\ell-1},2^{\ell})$. $\ell_{i}$ can be
negative and if $d(f^{*},\bar{F}(x_{i}))=0$, let $\ell_{i}=-\infty$. Observe
that $d(f^{*},\bar{F}(x_{i}))$ and $\ell_{i}$ are non-increasing in $i$. Let
$\tau$ be the largest integer $i$ with
$d(f^{*},\bar{F}(x_{i}))>\min\\{7\eta_{\infty},4w(f^{*})\\}$. Note that $\tau$
is a random variable. We refer to the demand sequence before $x_{\tau}$ as the
long-distance stage and the sequence after $x_{\tau}$ as the short-distance
stage. In this section, we focus on the case when $7\eta_{\infty}\leq
4w(f^{*})$. The proof for the other case is very similar and can be found in
Section 3.2.

##### Long-distance stage.

We start with bounding the total cost in the long-distance stage. Intuitively,
our procedure Pred would quickly build a facility that is close to $f^{*}$
within a distance of $O(\eta_{\infty})$, since it is guaranteed that for each
demand point $x_{i}$, the distance between $f^{*}$ and its corresponding
prediction $f_{x_{i}}^{\mathrm{pred}}$ is at most $\eta_{\infty}$. Formally,
we prove the following statements.

######  Lemma 3.6.

$\operatorname{\mathbb{E}}\left[\sum_{i<\tau}\operatorname{cost}_{\mathrm{M}}(x_{i})\right]\leq
2w(f^{*})$.

###### Proof.

Let $G=\\{g_{1},g_{2},\dots,g_{t}\\}$ be the facilities opened by the Pred
steps on the arrivals of all $\\{x_{i}\\}_{i<\tau}$, and are listed according
to their opening order. Observe that the budget that is assigned to the Pred
step is $\operatorname{cost}_{\mathrm{M}}(x_{i})$, and the expected opening
cost of each Pred step equals its budget. By the definition of $G$, we have
$\operatorname{\mathbb{E}}\left[\sum_{i<\tau}\operatorname{cost}_{\mathrm{M}}(x_{i})\right]=\operatorname{\mathbb{E}}\left[\sum_{k\in[t]}w(g_{k})\right].$

Next, we prove that the opening costs of $g_{k}$’s are always strictly
increasing. For each $k\in[t-1]$, suppose $g_{k}$ is opened on the arrival of
demand $x$ and $g_{k+1}$ is opened on the arrival of demand $y$. Let $F$
denote the set of all open facilities right before $g_{k+1}$ is opened. Let
$f:=\arg\min_{f:d(f_{y}^{\mathrm{pred}},f)\leq\frac{1}{2}d(f_{y}^{\mathrm{pred}},g_{k})}w(f)$,
we must have $w(g_{k+1})\geq w(f)$, since
$g_{k+1}=\arg\min_{f:d(f_{y}^{\mathrm{pred}},f)\leq\frac{1}{2}d(f_{y}^{\mathrm{pred}},F)}w(f)$
and that $d(f_{y}^{\mathrm{pred}},F)\leq d(f_{y}^{\mathrm{pred}},g_{k})$.
Moreover,

$d(f,f_{x}^{\mathrm{pred}})\leq
d(f,f_{y}^{\mathrm{pred}})+d(f_{x}^{\mathrm{pred}},f_{y}^{\mathrm{pred}})\leq\frac{1}{2}d(f_{y}^{\mathrm{pred}},g_{k})+2\eta_{\infty}\\\
\leq\frac{1}{2}\left(d(f_{x}^{\mathrm{pred}},g_{k})+d(f_{x}^{\mathrm{pred}},f_{y}^{\mathrm{pred}})\right)+2\eta_{\infty}\leq\frac{1}{2}d(f_{x}^{\mathrm{pred}},g_{k})+3\eta_{\infty}<d(f_{x}^{\mathrm{pred}},g_{k}).$

Here, the second and fourth inequalities use the fact that
$d(f_{x}^{\mathrm{pred}},f_{y}^{\mathrm{pred}})\leq
d(f_{x}^{\mathrm{pred}},f^{*})+d(f^{*},f_{y}^{\mathrm{pred}})\leq
2\eta_{\infty}$ since both $x,y\in X(f^{*})$. The last inequality follows from
the fact that $d(f_{x}^{\mathrm{pred}},g_{k})\geq
d(g_{k},f^{*})-d(f_{x}^{\mathrm{pred}},f^{*})>7\eta_{\infty}-\eta_{\infty}=6\eta_{\infty}$
by the definition of $\tau$.

Consider the moment when we open $g_{k}$, the fact that we do not open
facility $f$ implies that $w(g_{k})<w(f)$. Therefore, $w(g_{k})<w(f)\leq
w(g_{k+1})$. Recall that the opening cost of each facility is a power of $2$.
We have that $\sum_{k\in[t]}w(g_{k})\leq 2w(g_{t}).$

Finally, we prove that the opening cost $w(g_{t})$ is at most $w(f^{*})$.
Consider the moment when $g_{t}$ is open, let $x$ be the corresponding demand
point. Notice that

$d(f^{*},f_{x}^{\mathrm{pred}})\leq\eta_{\infty}<\frac{1}{2}d(f^{*},\bar{F}(x))\leq\frac{1}{2}d(f^{*},\bar{F}_{\mathrm{P}}(x)),$

by the definition of $\tau$. However, we open $g_{t}$ instead of $f^{*}$ on
Line 20 of our algorithm. It must be the case that $w(f^{*})\geq w(g_{t})$.

To conclude the proof, we have $\sum_{k\in[t]}w(g_{k})\leq 2w(g_{t})\leq
2w(f^{*}).$ ∎

######  Lemma 3.7.

$\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x_{\tau})]\leq
2w(f^{*})+2\sum_{i=1}^{m}d(x_{i},f^{*})$.

###### Proof.

We bound the opening cost and connection cost separately.

##### Opening cost.

By the algorithm, we know for every $1\leq i\leq m$,

$\displaystyle\operatorname{\mathbb{E}}\left[w(\hat{F}_{\mathrm{M}}(x_{i}))\textbf{1}(w(\hat{F}_{\mathrm{M}}(x_{i}))>w(f^{*}))\right]\leq\sum_{i>l^{*}}\frac{\delta_{i-1}-\delta_{i}}{2^{i}}\cdot
2^{i}=\delta_{l^{*}}\leq d(x_{i},f^{*}).$

Hence, using the fact that at most one facility is opened by Meyerson step for
each demand,

$\displaystyle\operatorname{\mathbb{E}}[w(\hat{F}_{\mathrm{M}}(x_{\tau}))]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\max_{f\in
F_{\mathrm{M}}(x_{m})}w(f)\right]\leq
w(f^{*})+\operatorname{\mathbb{E}}\left[\sum_{f\in
F_{\mathrm{M}}(x_{m}),w(f)>w(f^{*})}w(f)\right]$ $\displaystyle\leq
w(f^{*})+\sum_{i=1}^{m}d(x_{i},f^{*}).$

This finishes the analysis for the opening cost.

##### Connection cost.

We claim that $d(x_{\tau},F(x_{\tau}))\leq w(f^{*})+d(x_{\tau},f^{*})$ (with
probability 1).

Let $\delta_{0},\delta_{1},\ldots,\delta_{L}$ be defined as in our algorithm.
We assume
$\delta_{0}=d(x_{\tau},\bar{F}(x_{\tau}))>w(f^{*})+d(x_{\tau},f^{*})$, as
otherwise the claim holds immediately. Let
$k:=\max\\{k:\delta_{k}>w(f^{*})+d(x_{\tau},f^{*})\\}$. Then

$\displaystyle\quad\Pr[d(x_{\tau},F(x_{\tau}))\leq
w(f^{*})+d(x_{\tau},f^{*})]$
$\displaystyle=\min\left(\sum_{i=k+1}^{L}\frac{\delta_{i-1}-\delta_{i}}{2^{i}},1\right)\geq\min\left(\sum_{i=k+1}^{\ell^{*}}\frac{\delta_{i-1}-\delta_{i}}{2^{\ell^{*}}},1\right)=\min\left(\frac{\delta_{k}-\delta_{\ell^{*}}}{2^{\ell^{*}}},1\right)=1.$

Therefore,
$\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x_{\tau})]=\operatorname{\mathbb{E}}[w(\hat{F}_{\mathrm{M}}(x_{\tau}))]+\operatorname{\mathbb{E}}[d(f^{*},F(x_{\tau}))]\leq
2w(f^{*})+2\sum_{i=1}^{m}d(x_{i},f^{*})$, which concludes the proof. ∎

##### Short-distance stage.

Next, we bound the costs for the subsequence of demand points whose arrival is
after the event that some facility near $f^{*}$ is open. Formally, these
demand points are $x_{i}$’s with $i>\tau$. The analysis of this part is
conceptually similar to a part of the analysis of Meyerson’s algorithm.
However, ours is more refined in that it utilizes the already opened facility
that is near $f^{*}$ to get an improved
$O(\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}})$ ratio instead of $O(\log
n)$. Moreover, Meyerson did not provide the full detail of this analysis, and
our complete self-contained proof fills in this gap.

By the definition of $\tau$, we have $d(f^{*},\bar{F}(x_{i}))\leq
7\eta_{\infty}$ for such $i>\tau$. For integer $\ell$, let
$I_{\ell}=\\{i>\tau\mid\ell_{i}=\ell\\}$. Then for $t$ such that
$2^{t-1}>\min\\{7\eta_{\infty},4w(f^{*})\\}$, we have $I_{t}=\emptyset$. Let
$\underline{\ell}$ be the integer that
$\frac{\operatorname{OPT}}{n}\in[2^{\underline{\ell}-1},2^{\underline{\ell}})$,
and let $\overline{\ell}$ be the integer such that
$\min\\{7\eta_{\infty},4w(f^{*})\\}\in[2^{\overline{\ell}-1},2^{\overline{\ell}})$.
We partition all demand points with $i>\tau$ into groups
$I_{\leq\underline{\ell}-1},I_{\underline{\ell}},\ldots,I_{\overline{\ell}}$
according to $\ell_{i}$, where
$I_{\leq\underline{\ell}-1}=\bigcup_{\ell\leq\underline{\ell}-1}{I_{\ell}}$.

######  Lemma 3.8.

$\operatorname{\mathbb{E}}\left[\sum_{i\in
I_{\leq\underline{\ell}-1}}\operatorname{cost}_{\mathrm{M}}(x_{i})\right]\leq\frac{2|X(f^{*})|}{n}\cdot\operatorname{OPT}$.

###### Proof.

For $i\in I_{\leq\underline{\ell}-1}$, we have that its connection cost
$d(x_{i},F(x_{i}))\leq d(x_{i},\bar{F}(x_{i}))\leq
2^{\underline{\ell}-1}\leq\frac{\operatorname{OPT}}{n}$. Let
$\delta_{0},\delta_{1},\dots,\delta_{L}$ and $f_{1},\dots,f_{L}$ be defined as
in our algorithm upon $x_{i}$’s arrival. Then, its expected opening cost in
the Mey step equals

$\operatorname{\mathbb{E}}\left[w(\hat{F}_{\mathrm{M}}(x_{i}))\right]=\sum_{k\in[L]}\Pr\left[\hat{F}_{\mathrm{M}}(x_{i})=\\{f_{k}\\}\right]\cdot
w(f_{k})\leq\sum_{k\in[L]}\min\left(p_{k},1\right)\cdot 2^{k-1}\\\
\leq\sum_{k\in[L]}\min\left(\frac{\delta_{k-1}-\delta_{k}}{2^{k}},1\right)\cdot
2^{k-1}\leq\sum_{k\in[L]}\frac{\delta_{k-1}-\delta_{k}}{2}\leq\frac{\delta_{0}}{2}\leq\frac{\operatorname{OPT}}{2n}.$

To sum up,

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{i\in
I_{\leq\underline{\ell}-1}}\operatorname{cost}_{\mathrm{M}}(x_{i})\right]\leq\operatorname{\mathbb{E}}\left[\sum_{i\in
I_{\leq\underline{\ell}-1}}\left(d(x_{i},F(x_{i}))+w(\hat{F}_{\mathrm{M}}(x_{i}))\right)\right]$
$\displaystyle\leq\sum_{i\in
I_{\leq\underline{\ell}-1}}\frac{3}{2n}\operatorname{OPT}$
$\displaystyle<\frac{2|X(f^{*})|}{n}\cdot\operatorname{OPT}.$

∎

######  Lemma 3.9.

For every $\ell\in[\underline{\ell},\overline{\ell}]$,
$\operatorname{\mathbb{E}}\left[\sum_{i\in
I_{\ell}}\operatorname{cost}_{\mathrm{M}}(x_{i})\right]\leq 18\sum_{i\in
I_{\ell}}d(x_{i},f^{*})+32w(f^{*})$.

###### Proof.

Recall that we relabeled and restricted the indices of points in $X$ to
$X(f^{*})=\\{x_{1},\ldots,x_{m}\\}$. However, in this proof, we also need to
talk about the other points in the original data set (that do not belong to
$X(f^{*})$). Hence, to avoid confusions, we rewrite
$X=\\{y_{1},\ldots,y_{n}\\}$ (so $y_{1},\ldots,y_{n}$ are the demand points in
order), and we define $\sigma:[m]\to[n]$ that maps elements $x_{j}\in
X(f^{*})$ to its identity $y_{i}\in X$, i.e., $\sigma(j)=i$.

For $i\in[n]$, let

$\displaystyle
z^{\mathrm{M}}_{i}:=\begin{cases}\hat{F}_{\mathrm{M}}(y_{i})&\hat{F}_{\mathrm{M}}(y_{i})\neq\emptyset\\\
\text{none}&\text{otherwise}\end{cases},$

and define $z^{\mathrm{P}}_{i}$ similarly. Since the Mey step opens at most
one facility, $z^{\mathrm{M}}_{i}$ is either a singleton or “none”. Finally,
define $z_{i}:=z^{\mathrm{M}}_{i}\cup z^{\mathrm{P}}_{i}$.

Define $\tau_{\ell}=\min\\{i\in[n]\mid z^{\mathrm{M}}_{i}\neq\text{none and
}d(f^{*},z^{\mathrm{M}}_{i})<2^{\ell-1}\\}$, we have

$\operatorname{\mathbb{E}}\left[\sum_{i\in
I_{\ell}}\operatorname{cost}_{\mathrm{M}}(x_{i})-18d(x_{i},f^{*})\right]=\operatorname{\mathbb{E}}\left[\sum_{i\in[\tau_{\ell}]}\left(\operatorname{cost}_{\mathrm{M}}(y_{i})-18d(y_{i},f^{*})\right)\mathbf{1}(i\in\sigma(I_{\ell}))\right].$
(1)

Next, we prove a stronger version by induction, and the induction hypothesis
goes as follows. For every $j\in[n]$,

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{i=j}^{\tau_{\ell}}\left(\operatorname{cost}_{\mathrm{M}}(y_{i})-18d(y_{i},f^{*})\right)\mathbf{1}(i\in\sigma(I_{\ell}))\mid\mathcal{E}_{j-1}\right]\leq
32w(f^{*}),$

where $\mathcal{E}_{j}=(z_{1},\ldots,z_{j})$. Clearly, applying this with
$j=1$ implies (1), hence it suffices to prove this hypothesis.

##### Base case.

The base case is $j=n$, and we would do a backward induction on $j$. Since we
condition on $\mathcal{E}_{j-1}$, the variables $\delta_{0},\ldots,\delta_{L}$
in the Mey step of $y_{j}$, as well as wether or not $j\in\sigma(I_{\ell})$,
are fixed. Hence,

$\displaystyle\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(y_{j})\mid\mathcal{E}_{j-1}]\leq
d(y_{j},\bar{F}(y_{j}))+\sum_{i=1}^{L}\frac{\delta_{i-1}-\delta_{i}}{2^{i}}\cdot
2^{i}\leq 2d(y_{j},\bar{F}(y_{j})).$

This implies

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{i=j}^{\tau_{\ell}}\left(\operatorname{cost}_{\mathrm{M}}(y_{i})-18d(y_{i},f^{*})\right)\mathbf{1}(i\in\sigma(I_{\ell}))\mid\mathcal{E}_{j-1}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}[(\operatorname{cost}_{\mathrm{M}}(y_{n})-18d(y_{n},f^{*}))\mathbf{1}(n\in\sigma(I_{\ell}))\mid\mathcal{E}_{n-1}]$
$\displaystyle\leq
2d(y_{n},\bar{F}(y_{n}))-18d(y_{n},f^{*})\mid_{n\in\sigma(I_{\ell})}$
$\displaystyle\leq
2d(y_{n},\bar{F}(y_{n}))-2d(y_{n},f^{*})\mid_{n\in\sigma(I_{\ell})}$
$\displaystyle\leq 2d(\bar{F}(y_{n}),f^{*})\mid_{n\in\sigma(I_{\ell})}$
$\displaystyle\leq 2^{\ell+1}\leq 2^{\ell^{*}+1}\leq O(w(f^{*})).$

##### Inductive step.

Next, assume the hypothesis holds for $j+1,j+2,\ldots,n$, and we would prove
the hypothesis for $j$. We proceed with the following case analysis.

##### Case 1:

$j\notin\sigma(I_{\ell})$. We do a conditional expectation argument, and we
have

$\displaystyle\qquad\operatorname{\mathbb{E}}\left[\sum_{i=j}^{\tau_{\ell}}\left(\operatorname{cost}_{\mathrm{M}}(y_{i})-18d(y_{i},f^{*})\right)\mathbf{1}(i\in\sigma(I_{\ell}))\mid\mathcal{E}_{j-1}\right]$
$\displaystyle=\sum_{z^{\mathrm{M}}_{j},z^{\mathrm{P}}_{j}}\Pr\left[z^{\mathrm{M}}_{j},z^{\mathrm{P}}_{j}\mid\mathcal{E}_{j-1}\right]\operatorname{\mathbb{E}}\left[\sum_{i=j}^{\tau_{\ell}}\left(\operatorname{cost}_{\mathrm{M}}(y_{i})-18d(y_{i},f^{*})\right)\mathbf{1}(i\in\sigma(I_{\ell}))\mid\mathcal{E}_{j-1},z^{\mathrm{M}}_{j},z^{\mathrm{P}}_{j}\right]$
$\displaystyle\leq 32w(f^{*}).$

where the second step follows by induction hypothesis.

##### Case 2:

$j\in I_{\ell}$ and $8d(y_{j},f^{*})>d(f^{*},\bar{F}(y_{j}))$. We have

$\displaystyle d(y_{j},F(y_{j}))\leq d(y_{j},f^{*})+d(f^{*},F(y_{j}))\leq
9d(y_{j},f^{*}).$

Hence
$\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(y_{j})-18d(y_{j},f^{*})]\leq
0$, and the hypothesis follows from a similar argument as in Case 1.

##### Case 3:

$j\in I_{\ell}$, and $8d(y_{j},f^{*})\leq d(f^{*},\bar{F}(y_{j}))$. We have

$\delta_{\ell^{*}}\leq
d(y_{j},f^{*})\leq\frac{1}{8}d(f^{*},\bar{F}(y_{j}))\leq 2^{\ell-3}.$

Let $D=\\{f:d(f^{*},f)\geq 2^{\ell-1}\\}\cup\\{\text{none}\\}$. Let
$k=\min\\{k^{\prime}\mid\delta_{k^{\prime}}\leq 2^{\ell-2}\\}$. Then $\forall
i\geq k$, $d(f_{i},f^{*})\leq d(y_{j},f_{i})+d(y_{j},f^{*})<2^{\ell-1}$.

$\displaystyle\Pr\left[\tau_{\ell}\leq j\mid\mathcal{E}_{j-1}\right]$
$\displaystyle\geq\Pr\left[z^{\mathrm{M}}_{j}\notin
D\mid\mathcal{E}_{j-1}\right]\geq\Pr\left[f_{i}\text{ is open for some }i\geq
k\mid\mathcal{E}_{j-1}\right]$ $\displaystyle=\min\left(\sum_{i\geq
k}p_{i},1\right)=\min\left(\sum_{i\geq
k}\frac{\delta_{i-1}-\delta_{i}}{2^{i}},1\right)$
$\displaystyle\geq\min\left(\frac{\delta_{k-1}-\delta_{\ell^{*}}}{2^{\ell^{*}}},1\right)\geq\min\left(\frac{2^{\ell-2}-2^{\ell-3}}{2^{\ell^{*}}},1\right)\geq\min\left(2^{\ell-3-\ell^{*}},1\right)$
$\displaystyle\geq\frac{\delta_{0}}{16w(f^{*})}\geq\frac{\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(y_{j})\mid\mathcal{E}_{j-1}]}{32w(f^{*})},$

where the second last inequality follows from
$\delta_{0}=d(y_{j},\bar{F}(y_{j}))\leq 2^{\ell}$ and
$w(f^{*})=2^{\ell^{*}-1}$. Thus,

$\displaystyle\text{LHS}=\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(y_{j})\mid\mathcal{E}_{j-1}]$
$\displaystyle+\sum_{t_{j}\in
D}\sum_{z^{\mathrm{P}}_{j}}\Pr[z^{\mathrm{M}}_{j}=t_{j},z^{\mathrm{P}}_{j}\mid\mathcal{E}_{j-1}]\operatorname{\mathbb{E}}\left[\sum_{i=j+1}^{\tau_{\ell}}\left(\operatorname{cost}_{\mathrm{M}}(y_{i})-18d(y_{i},f^{*})\right)\mathbf{1}(i\in\sigma(I_{\ell}))\mid\mathcal{E}_{j-1},z^{\mathrm{M}}_{j}=t_{j},z^{\mathrm{P}}_{j}\right]$
$\displaystyle\leq\Pr\left[z^{\mathrm{M}}_{j}\notin
D\mid\mathcal{E}_{j-1}\right]\cdot 32w(f^{*})+\Pr\left[z^{\mathrm{M}}_{j}\in
D\mid\mathcal{E}_{j-1}\right]\cdot 32w(f^{*})$ $\displaystyle\leq 32w(f^{*}),$

where the second step follows by induction hypothesis. In summary, we have

$\operatorname{\mathbb{E}}\left[\sum_{i=1}^{\tau_{\ell}}\left(\operatorname{cost}_{\mathrm{M}}(y_{i})-18d(y_{i},f^{*})\right)\mathbf{1}(i\in\sigma(I_{\ell}))\mid\mathcal{E}_{j-1}\right]\leq
32w(f^{*})$

∎

##### Proof of Lemma 3.5.

We conclude Lemma 3.5 by combining Lemma 3.6, 3.7, 3.8, and 3.9.

$\displaystyle\sum_{i\in[m]}\operatorname{\mathbb{E}}\left[\operatorname{cost}_{\mathrm{M}}(x_{i})\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{i\in[\tau-1]}\operatorname{cost}_{\mathrm{M}}(x_{i})\right]+\operatorname{\mathbb{E}}[\operatorname{cost}_{\mathrm{M}}(x_{\tau})]$
$\displaystyle\qquad+\sum_{\ell=\underline{\ell}}^{\overline{\ell}}\operatorname{\mathbb{E}}\left[\sum_{i\in
I_{\ell}}\operatorname{cost}_{\mathrm{M}}(x_{i})\right]+\sum_{i\in
I_{\leq\underline{\ell}-1}}\operatorname{\mathbb{E}}\left[\operatorname{cost}_{\mathrm{M}}(x_{i})\right]$
$\displaystyle\leq
2w(f^{*})+\left(2w(f^{*})+2\sum_{i=1}^{m}d(x_{i},f^{*})\right)$
$\displaystyle\qquad+\sum_{\ell=\underline{\ell}}^{\overline{\ell}}\left(18\sum_{i\in
I_{\ell}}d(x_{i},f^{*})+32w(f^{*})\right)+\frac{2|X(f^{*})|}{n}\cdot\operatorname{OPT}$
$\displaystyle\leq\left(O(\overline{\ell}-\underline{\ell})+O(1)\right)\cdot\left(\sum_{i\in[m]}d(x_{i},f^{*})+w(f^{*})\right)+\frac{2|X(f^{*})|}{n}\operatorname{OPT}$
$\displaystyle\leq
O\left(\max\left\\{1,\log\frac{n\eta_{\infty}}{\operatorname{OPT}}\right\\}\right)\cdot\left(\sum_{i\in[m]}d(x_{i},f^{*})+w(f^{*})\right)+O\left(\frac{|X(f^{*})|}{n}\operatorname{OPT}\right).$

∎

###  3.2 Proof of Lemma 3.5: When $7\eta_{\infty}>4w(f^{*})$

The proof is mostly the same as in the other case which we prove in Section
3.1, and we only highlight the key differences. We use the same definition for
parameters $\tau$, $\underline{\ell}$, and $\overline{\ell}$. It can be
verified that Lemma 3.7, 3.8 and 3.9 still holds and their proof in Section
3.1 still works.

However, Lemma 3.6 relies on that $7\eta_{\infty}\leq 4w(f^{*})$, which does
not work in the current case. We provide Lemma 3.11 in replacement of Lemma
3.6, which offers a slightly different bound but it still suffices for Lemma
3.5.

######  Lemma 3.10.

For every $i<\tau$, $d(x_{i},f^{*})\geq w(f^{*})$.

###### Proof.

We prove the statement by contradiction. Suppose $d(x_{i},f^{*})<w(f^{*})$.
Let $\delta_{0},\delta_{1},\ldots,\delta_{W}$ be defined as in our algorithm.
Then, we have

$\delta_{0}=d(x_{i},\bar{F}(x_{i}))\geq
d(f^{*},\bar{F}(x_{i}))-d(f^{*},x_{i})\geq
d(f^{*},\bar{F}(x_{i}))-w(f^{*})>3w(f^{*}),$

where the last inequality follows from the definition of $\tau$ that
$d(f^{*},\bar{F}(x_{i}))>4w(f^{*})$. Let $k=\min\\{k\mid\delta_{k}\leq
3w(f^{*})\\}$. We have $k\geq 1$. We prove that a facility within a distance
of $3w(f^{*})$ from $x_{i}$ must be open at this step.

$\displaystyle\Pr\left[d(x_{i},F(x_{i}))\leq 3w(f^{*})\right]$
$\displaystyle\geq\Pr\left[f_{j}\text{ is opened for some }j\geq k\right]$
$\displaystyle\geq\min\left(\sum_{j\geq
k}p_{k},1\right)\geq\min\left(\sum_{j=k}^{\ell^{*}}\frac{\delta_{j-1}-\delta_{j}}{2^{j}},1\right)$
$\displaystyle\geq\min\left(\frac{\delta_{k-1}-\delta_{\ell^{*}}}{2^{\ell^{*}}},1\right)\geq\min\left(\frac{3w(f^{*})-w(f^{*})}{2^{\ell^{*}}},1\right)=1,$

where the last inequality uses the fact that $\delta_{\ell^{*}}\leq
d(x_{i},f^{*})\leq w(f^{*})$. Consequently,

$d(f^{*},\hat{F}(x_{i+1}))\leq d(f^{*},F(x_{i}))\leq
d(x_{i},F(x_{i}))+d(x_{i},f^{*})<4w(f^{*}),$

which contradicts the definition of $\tau$. ∎

######  Lemma 3.11.

$\operatorname{\mathbb{E}}\left[\sum_{i\in[\tau]}\operatorname{cost}(x_{i})\right]\leq
6\operatorname{\mathbb{E}}[\sum_{i\in[\tau]}d(x_{i},f^{*})]+4\cdot w(f^{*})$.

###### Proof.

On the arrival of $x_{i}$ for each $i\in[\tau]$, let
$\delta_{0},\delta_{1},\ldots,\delta_{L}$ be defined as in our algorithm. We
first study the connecting cost of request $x_{i}$. We have

$d(x_{i},F(x_{i}))\leq\max\left(d(x_{i},F(x_{j})\backslash\hat{F}(x_{i})),d(x_{i},\hat{F}(x_{i}))\right)=\max\left(\delta_{0},d(x_{i},\hat{F}(x_{i}))\right).$

We prove this value is at most $d(x_{i},f^{*})+2w(f^{*})$. Suppose
$\delta_{0}>d(x_{i},f^{*})+2w(f^{*})$, as otherwise the statement holds.
Recall that $\delta_{j}$ is non-increasing, let $k=\min\\{k\mid\delta_{k}\leq
d(x_{i},f^{*})+2w(f^{*})\\}.$ By the definition of $k$, we have that

$\Pr\left[d(x_{i},F(x_{i}))\leq
d(x_{i},f^{*})+2w(f^{*})\right]\geq\Pr[f_{j}\text{ is opened for some }j\geq
k]\\\ \geq\min\left(\sum_{j\geq k}p_{j},1\right)\geq\min\left(\sum_{j\geq
k}^{\ell^{*}}\frac{\delta_{j-1}-\delta_{j}}{2^{j}},1\right)\geq\min\left(\frac{\delta_{k-1}-\delta_{\ell^{*}}}{2^{\ell^{*}}},1\right)\\\
\geq\min\left(\frac{d(x_{i},f^{*})+2w(f^{*})-\delta_{\ell^{*}}}{2^{\ell^{*}}},1\right)\geq\min\left(\frac{w(f^{*})}{2^{\ell^{*}-1}},1\right)=1.$

To sum up, we have shown that the connecting cost $d(x_{i},F(x_{i}))\leq
d(x_{i},f^{*})+2w(f^{*})$.

Next, we study the expected opening cost
$\operatorname{\mathbb{E}}[w(\hat{F}(x_{i}))]$. We have

$\operatorname{\mathbb{E}}[w(\hat{F}(x_{i}))]=\sum_{j\in[L]}\Pr\left[\hat{F}(x_{i})=\\{f_{j}\\}\right]\cdot
w(f_{j})\leq\sum_{j\in[L]}\min\left(\frac{\delta_{j-1}-\delta_{j}}{2^{j}},1\right)\cdot
2^{j-1}\\\
\leq\sum_{j\leq\ell^{*}}2^{j-1}+\sum_{j>\ell^{*}}\frac{\delta_{j-1}-\delta_{j}}{2^{j}}\cdot
2^{j-1}<2^{\ell^{*}}+\frac{1}{2}\delta_{\ell^{*}}<2w(f^{*})+d(x_{i},f^{*}).$

By Lemma 3.10, we conclude the proof of the statement:

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{i\in[\tau]}\operatorname{cost}(x_{i})\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{i\in[\tau]}\left(d(x_{i},F(x_{i}))+w(\hat{F}(x_{i}))\right)\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\sum_{i\in[\tau]}\left(2d(x_{i},f^{*})+4w(f^{*})\right)\right]$
$\displaystyle\leq
6\operatorname{\mathbb{E}}\left[\sum_{i<\tau}d(x_{i},f^{*})+\left(2d(x_{\tau},f^{*})+4w(f^{*})\right)\right]$
$\displaystyle\leq
6\operatorname{\mathbb{E}}\left[\sum_{i\in[\tau]}d(x_{i},f^{*})\right]+4w(f^{*}).$

∎

##  4 Lower Bound

In the classical online facility location problem, a tight lower bound of
$O(\frac{\log n}{\log\log n})$ is established by Fotakis (2008), even for the
special case when the facility cost is uniform and the metric space is a
binary hierarchically well-separated tree (HST). We extend their construction
to the setting with predictions, proving that when the predictions are not
precise (i.e. $\eta_{\infty}>0$), achieving a competitive ratio of
$o(\frac{\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}}}{\log{\log{n}}})$ is
impossible.

######  Theorem 4.1.

Consider OFL with predictions with a uniform opening cost of $1$. For every
$\eta_{\infty}\in(0,1]$, there exists a class of inputs, such that no
(randomized) online algorithm is
$o(\frac{\log\frac{n\eta_{\infty}}{\operatorname{OPT}}}{\log\log
n})$-competitive, even when $\eta_{1}=O(1)$.

Before we provide the proof of our theorem, we give some implications of our
theorem. First of all, we normalize the opening cost to be $1$. Consequently,
the optimal cost is at least $1$. Furthermore, we are only interested in the
case when $\eta_{\infty}\leq 1$. Indeed, the optimal facility for each demand
point must be within a distance of $1$, as otherwise, we can reduce the cost
by opening a new facility at the demand point. Therefore, we can without loss
of generality to study predictions with $\eta_{\infty}=O(1)$. Without the
normalization, our theorem implies an impossibility result of
$o(\frac{\log\frac{n\eta_{\infty}}{\operatorname{OPT}}}{\log\log n})$ for
online facility location with predictions.

Moreover, recall the definition of total prediction error
$\eta_{1}=\sum_{i=1}^{n}{d(f_{x_{i}}^{\mathrm{pred}},f_{x_{i}}^{\mathrm{opt}})}$,
which is at least
$\eta_{\infty}=\max_{i}d(f_{x_{i}}^{\mathrm{pred}},f_{x_{i}}^{\mathrm{opt}})$.
Our theorem states that even when the total error $\eta_{1}$ is constant times
larger than the opening cost of $1$, there is no hope for a good algorithm.
Note that our bound above holds for any constant value of $\eta_{\infty}$. As
an implication, our construction rules out the possibility of an
$o(\frac{\log\frac{\eta_{1}}{\operatorname{OPT}}}{\log\log n})$-competitive
algorithm.

###### Proof.

By Yao’s principle, the expected cost of a randomized algorithm on the worst-
case input is no better than the expected cost for a worst-case probability
distribution on the inputs of the deterministic algorithm that performs best
against that distribution. For each $\eta_{\infty}$, we shall construct a
family of randomized instance, so that the expected cost of any deterministic
algorithm is at least
$\Omega(\frac{\log{\frac{n\eta_{\infty}}{\operatorname{OPT}}}}{\log{\log{n}}})$-competitive.

We first import the construction for the classical online facility location
problem by Fotakis (2008). Consider a hierarchically well-separated perfect
binary tree. Let the distance between root and its children as $D$. For every
vertex $i$ of the tree, the distance between $i$ and its children is
$\frac{1}{m}$ times the distance between $i$ and its parent. That is to say,
the distance between a height $i$ vertex and its children of height $i+1$ is
$\frac{D}{m^{i}}$. Let the height of the tree be $h$.

The demand sequence is consisted of $h+1$ phases. For each $0\leq i\leq h$, in
the $(i+1)$-th phase, $m^{i}$ demand points arrive consecutively at some
vertex of height $i$. For $i\geq 1$, the identity of the height $i$ vertex is
independently and uniformly chosen between the two children of $i$-th phase
vertex.

Consider the solution that opens only one facility at the leaf node that is
the $(h+1)$-th phase demand vertex and assign all demand points to the leaf.
The cost of this solution equals

$1+\sum\limits_{i=0}^{h}m^{i}\sum\limits_{j=i}^{h-1}\frac{D}{m^{j}}\leq
1+\sum\limits_{i=0}^{h-1}m^{i}\frac{D}{m^{i}}\frac{m}{m-1}=1+hD\frac{m}{m-1}.$

This value serves as an upper bound of the optimal cost. I.e.,
$\operatorname{OPT}\leq 1+hD\frac{m}{m-1}$.

Next, we describe the predictions associated with the demand points.
Intuitively, we try the best to hide the identity of the leaf node in the last
phase. We denote the leaf node as $f^{*}$, which is also the open facility in
the above described solution. Our prediction is produced according to the
following rule. When the distance between the current demand point and $f^{*}$
is less than $\eta_{\infty}$, let the prediction be the same as the demand
vertex. Otherwise, let the prediction be the vertex on the path from the
current demand point to $f^{*}$, whose distance to $f^{*}$ equals
$\eta_{\infty}$.

We prove a lower bound on the expected cost of any deterministic algorithm. We
first overlook the first a few phases until the subtree of the current demand
vertex has diameter less than $\eta_{\infty}$. Let it be the $h^{\prime}$-th
phase. We now focus on the cost induced after the $h^{\prime}$-th phase and
notice that the predictions are useless as they are just the demand points.
When the $m^{i}$ demand points at vertex of height $i$ comes, we consider the
following two cases:

##### Case 1:

There is no facility opened in the current subtree. Then we either open a new
facility bearing an opening cost $1$ or assign the current demands to
facilities outside the subtree bearing a large connection cost at least
$\frac{D}{m^{i-1}}$ per demand. So the cost of this vertex is
$\min\\{1,Dm\\}$.

##### Case 2:

There has been at least one facility opened in the current subtree. Since the
next vertex is uniformly randomly chosen in its two children, the expected
number of facility that will not enter the next phase subtree is at
least$\frac{1}{2}$. We call it abandoned. The expected sum of abandoned
facility is $\frac{1}{2}$ of the occurrence of case 2. Thus the expected cost
in every occurrence of case 2 is $\frac{1}{2}$.

We carefully choose $D,m,h$ so that 1) $mD=1$; 2) the total number of demand
points is $n$, i.e. $\sum\limits_{i=0}^{h}m^{i}=n$; and
3)$\frac{D}{m^{h^{\prime}}}=\eta_{\infty}$. These conditions give that
$(h+1)\log{m}=\log{n}$, $(h^{\prime}+1)\log{m}=-\log{\eta_{\infty}}$.
Consequently, $h-h^{\prime}=\frac{\log{n\eta_{\infty}}}{\log{m}}$.

To sum up, an lower bound of any deterministic algorithm is
$(h-h^{\prime})\min\\{\frac{1}{2},mD\\}=\Omega\left(\frac{\log{n\eta_{\infty}}}{\log{m}}\right)$,
while the optimal cost is at most
$1+hD\frac{m}{m-1}=O\left(\frac{\log{n}}{m\log{m}}\right)$. Setting
$m=\frac{\log{n}}{\log{\log{n}}}$, the optimal cost is $O(1)$. And we prove
the claimed lower bound of
$\Omega(\frac{\log{n\eta_{\infty}}}{\log{\log{n}}})$. Finally, it is
straightforward to see that the summation of the prediction error
$\eta_{1}\leq\operatorname{OPT}=O(1)$. ∎

##  5 Experiments

We validate our online algorithms on various datasets of different types. In
particular, we consider three Euclidean data sets, a) Twitter (Chan et al., ),
b) Adult (Dua & Graff, 2017), and c) Non-Uni (Cebecauer & Buzna, 2018) which
are datasets consisting of numeric features in $\mathbb{R}^{d}$ and the
distance is measured by $\ell_{2}$, and one graph dataset, US-PG (Rossi &
Ahmed, 2015) which represents US power grid in a graph, where the points are
vertices in a graph and the distance is measured by the shortest path
distance. The opening cost is non-uniform in Non-Uni dataset, while it is
uniform in all the other three. These datasets have also been used in previous
papers that study facility location and related clustering problems
(Chierichetti et al., 2017; Chan et al., 2018; Cohen-Addad et al., 2019). A
summary of the specification of datasets can be found in Table 1.

Table 1: Specifications of datasets dataset | type | size | # of dimension/edges | non-uniform
---|---|---|---|---
Twitter | Euclidean | 30k | # dimension = 2 | no
Adult | Euclidean | 32k | # dimension = 6 | no
US-PG | Graph | 4.9k | # edges = 6.6k | no
Non-Uni | Euclidean | 4.8k | # dimension = 2 | yes

##### Tradeoff between $\eta_{\infty}$ and empirical competitive ratio.

Our first experiment aims to measure the tradeoff between $\eta_{\infty}$ and
the empirical competitive ratio of our algorithm, and we compare against two
“extreme” baselines, a) the vanilla Meyerson’s algorithm _without using_
predictions which we call Meyerson, and b) a naive algorithm that _always
follows_ the prediction which we call Follow-Predict. Intuitively, a
simultaneously consistent and robust online algorithm should perform similarly
to the Follow-Predict baseline when the prediction is nearly perfect, while
comparable to Meyerson when the prediction is of low quality.

Since it is NP-hard to find the optimal solution to facility location problem,
we run a simple 3-approximate MP algorithm (Mettu & Plaxton, 2000) to find a
near optimal solution $F^{\star}$ for every dataset, and we use this solution
as the offline optimal solution (which we use as the benchmark for the
competitive ratio). Then, for a given $\eta_{\infty}$ and a demand point $x$,
we pick a random facility $f\in\mathcal{F}$ such that $\eta_{\infty}/2\leq
d(f,F^{\star}_{x})\leq\eta_{\infty}$ as the prediction, where $F^{\star}_{x}$
is the point in $F^{\star}$ that is closest to $x$. The empirical competitive
ratio is evaluated for every baselines as well as our algorithm on top of
every dataset, subject to various values of $\eta_{\infty}$.

All our experiments are conducted on a laptop with Intel Core i7 CPU and 16GB
memory. Since the algorithms are randomized, we repeat every run 10 times and
take the average cost.

In Figure 1 we plot for every dataset a line-plot for all baselines and our
algorithm, whose x-axis is $\eta_{\infty}$ and y-axis is the empirical
competitive ratio. Here, the scale of x-axis is different since
$\eta_{\infty}$ is dependent on the scale of the dataset. From Figure 1, it
can be seen that our algorithm performs consistently better than Meyerson when
$\eta_{\infty}$ is relatively small, and it has comparable performance to
Meyerson when $\eta_{\infty}$ is so large that the Follow-Predict baseline
loses control of the competitive ratio. For instance, in the Twitter dataset,
our algorithm performs better than Meyerson when $\eta_{\infty}\leq 2$, and
when $\eta_{\infty}$ becomes larger, our algorithm performs almost the same
with Meyerson while the ratio of Follow-Predict baseline increases rapidly.

Twitter dataset

Adult dataset

US-PG dataset

Non-Uni dataset

Figure 1: The tradeoff between prediction error $\eta_{\infty}$ and empirical
competitive ratio over four datasets: Twitter, Adult, US-GD and Non-Uni.

Furthermore, we observe that our performance lead over Meryerson is especially
significant on dataset Non-Uni whose opening cost is non-uniform. This
suggests that our algorithm manages to use the predictions effectively in the
non-uniform setting, even provided that the prediction is tricky to use since
predictions at “good” locations could have large opening costs. In particular,
our algorithm does a good job to find a “nearby” facility that has the correct
opening cost and location tradeoff.

##### A simple predictor and its empirical performance.

We also present a simple predictor that can be constructed easily from a
training set, and evalute its performance on our datasets. We assume the
predictor has access to a training set $T$. Initially, the predictor runs the
3-approximate MP algorithm on the training set $T$ to obtain a solution
$F^{*}$. Then when demand points from the dataset (i.e., test set) $X$
arrives, the predictor periodically reruns the MP algorithm, on the union of
$T$ and the already-seen test data $X^{\prime}\subseteq X$, and update
$F^{*}$. For a demand point $x$, the prediction is defined as the nearest
facility to $x$ in $F^{*}$.

To evaluate the performance of this simple predictor, we take a random sample
of 30% points from the dataset as the training set $T$, and take the remaining
70% as the test set $X$. We list the accuracy achieved by the predictor in
this setup in Table 2. From the table, we observe that the predictor achieves
a reasonable accuracy since the ratio of Follow-Predict baseline is comparable
to Meyerson’s algorithm. Moveover, when combining with this predictor, our
algorithm outperforms both baselines, especially on the Non-Uni dataset where
the improvement is almost two times. This not only shows the effectiveness of
the simple predictor, but also shows the strength of our algorithm.

Finally, we emphasize that this simple predictor, even without using any
advanced machine learning techniques or domain-specific signals/features from
the data points (which are however commonly used in designing predictors),
already achieves a reasonable performance. Hence, we expect to see an even
better result if a carefully engineered predictor is employed.

Table 2: Empirical competitive ratio evaluation for the simple predictor dataset | Meyerson | Follow-Predict | Ours
---|---|---|---
Twitter | 1.70 | 1.69 | 1.57
Adult | 1.55 | 1.57 | 1.49
US-PG | 1.47 | 1.47 | 1.43
Non-Uni | 5.66 | 5.7 | 2.93

#### Acknowledgments

This work is supported by Science and Technology Innovation 2030 — “New
Generation of Artificial Intelligence” Major Project No.(2018AAA0100903),
Program for Innovative Research Team of Shanghai University of Finance and
Economics (IRTSHUFE) and the Fundamental Research Funds for the Central
Universities. Shaofeng H.-C. Jiang is supported in part by Ministry of Science
and Technology of China No. 2021YFA1000900. Zhihao Gavin Tang is partially
supported by Huawei Theory Lab. We thank all anonymous reviewers’ for their
insightful comments.

## References

  * Ahmadi-Javid et al. (2017) Amir Ahmadi-Javid, Pardis Seyedi, and Siddhartha S. Syam.  A survey of healthcare facility location.  _Comput. Oper. Res._ , 79:223–263, 2017.
  * Antoniadis et al. (2020) Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  In _NeurIPS_ , 2020.
  * Azar et al. (2021) Yossi Azar, Stefano Leonardi, and Noam Touitou.  Flow time scheduling with uncertain processing time.  In _STOC_ , pp. 1070–1080, 2021.
  * Bamas et al. (2020a) Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson.  Learning augmented energy minimization via speed scaling.  In _NeurIPS_ , 2020a.
  * Bamas et al. (2020b) Étienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  In _NeurIPS_ , 2020b.
  * Cebecauer & Buzna (2018) Matej Cebecauer and L’uboš Buzna.  Large-scale test data set for location problems.  _Data in brief_ , 17:267–274, 2018.
  * Chan et al. (2018) T.-H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio.  Fully dynamic _k_ -center clustering.  In _WWW_ , pp. 579–587. ACM, 2018.
  * (8) T. Hubert Chan, A. Guerqin, and M. Sozio.  Twitter data set.  URL https://github.com/fe6Bc5R4JvLkFkSeExHM/k-center.
  * Chierichetti et al. (2017) Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii.  Fair clustering through fairlets.  In _NIPS_ , pp. 5029–5037, 2017.
  * Cohen-Addad et al. (2019) Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn.  Fully dynamic consistent facility location.  In _NeurIPS_ , pp. 3250–3260, 2019.
  * Divéki & Imreh (2011) Gabriella Divéki and Csanád Imreh.  Online facility location with facility movements.  _Central Eur. J. Oper. Res._ , 19(2):191–200, 2011.
  * Drezner & Hamacher (2002) Zvi Drezner and Horst W. Hamacher.  _Facility location - applications and theory_.  Springer, 2002.
  * Dua & Graff (2017) Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL https://archive.ics.uci.edu/ml/datasets/adult.
  * Dütting et al. (2021) Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii.  Secretaries with advice.  In _EC_ , pp. 409–429, 2021.
  * Eisenstat et al. (2014) David Eisenstat, Claire Mathieu, and Nicolas Schabanel.  Facility location in evolving metrics.  In _ICALP_ , volume 8573, pp. 459–470, 2014.
  * Fotakis (2008) Dimitris Fotakis.  On the competitive ratio for online facility location.  _Algorithmica_ , 50(1):1–57, 2008.
  * Fotakis et al. (2021a) Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris.  Learning augmented online facility location.  _CoRR_ , abs/2107.08277, 2021a.
  * Fotakis et al. (2021b) Dimitris Fotakis, Loukas Kavouras, and Lydia Zakynthinou.  Online facility location in evolving metrics.  _Algorithms_ , 14(3):73, 2021b.
  * Gollapudi & Panigrahi (2019) Sreenivas Gollapudi and Debmalya Panigrahi.  Online algorithms for rent-or-buy with expert advice.  In _ICML_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 2319–2327. PMLR, 2019.
  * Jiang et al. (2021) Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang.  Online selection problems against constrained adversary.  In _ICML_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 5002–5012. PMLR, 2021.
  * Klose & Drexl (2005) Andreas Klose and Andreas Drexl.  Facility location models for distribution system design.  _Eur. J. Oper. Res._ , 162(1):4–29, 2005.
  * Laporte et al. (2019) Gilbert Laporte, Stefan Nickel, and Francisco Saldanha da Gama.  _Location science_.  Springer, 2019.
  * Lattanzi et al. (2020) Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In _SODA_ , pp. 1859–1877, 2020.
  * Lykouris & Vassilvitskii (2021) Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  _J. ACM_ , 68(4):24:1–24:25, 2021.
  * Medina & Vassilvitskii (2017) Andres Muñoz Medina and Sergei Vassilvitskii.  Revenue optimization with approximate bid predictions.  In _NIPS_ , pp. 1858–1866, 2017.
  * Melo et al. (2009) M. Teresa Melo, Stefan Nickel, and Francisco Saldanha-da-Gama.  Facility location and supply chain management - A review.  _Eur. J. Oper. Res._ , 196(2):401–412, 2009.
  * Mettu & Plaxton (2000) Ramgopal R. Mettu and C. Greg Plaxton.  The online median problem.  In _FOCS_ , pp. 339–348. IEEE Computer Society, 2000.
  * Meyerson (2001) Adam Meyerson.  Online facility location.  In _FOCS_ , pp. 426–431. IEEE Computer Society, 2001.
  * Panconesi et al. (2021) Alessandro Panconesi, Flavio Chierichetti, Giuseppe Re, Matteo Almanza, and Silvio Lattanzi.  Online facility location with multiple advice.  In _NeurIPS 2021_ , 2021.
  * Purohit et al. (2018) Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ML predictions.  In _NeurIPS_ , pp. 9684–9693, 2018.
  * Rohatgi (2020) Dhruv Rohatgi.  Near-optimal bounds for online caching with machine learned advice.  In _SODA_ , pp. 1834–1845. SIAM, 2020.
  * Rossi & Ahmed (2015) Ryan A. Rossi and Nesreen K. Ahmed.  The network data repository with interactive graph analytics and visualization.  In _AAAI_ , 2015.  URL http://networkrepository.com.
  * Wei & Zhang (2020) Alexander Wei and Fred Zhang.  Optimal robustness-consistency trade-offs for learning-augmented online algorithms.  In _NeurIPS_ , 2020.

##  Appendix A $t$-Outlier Setting

Observe that our main error parameter $\eta_{\infty}$ could be very sensitive
to a single outlier prediction that has a large error. To make the error
parameter bahave more smoothly, we introduce an integer parameter $1\leq t\leq
n$, and define $\eta^{(t)}_{\infty}$ as the $t$-th largest prediction error,
i.e., the maximum prediction error excluding the $t-1$ high-error outliers.
Define $\eta^{(t)}_{1}$ similarly.

In the following, stated in Theorem A.1, we argue that our algorithm, without
any modification (but with an improved analysis), actually has a ratio of
$O(\log(1+t)+\log{\frac{n\eta^{(t)}_{\infty}}{\operatorname{OPT}}})$ that
holds for _every_ $t$. This also means the ratio would be $\min_{1\leq t\leq
n}{O(\log(1+t)+\log{\frac{n\eta^{(t)}_{\infty}}{\operatorname{OPT}}})}$, and
this is clearly a generalization of Theorem 1.1, since
$\eta^{(t)}_{\infty}=\eta_{\infty}$ when $t=1$.

Moreover, we note that our lower bound, Theorem 1.2, is still valid for ruling
out the possibility of replacing $\eta^{(t)}_{\infty}$ with $\eta^{(t)}_{1}$
in the abovementioned ratio, since one can still apply Theorem 1.2 with $t=1$.
However, it is an interesting open question to explore whether or not an
algorithm with a ratio like
$O(\log{t}+\frac{\eta^{(t)}_{1}}{\operatorname{OPT}})$ for some _specific_ $t$
(e.g., $t\geq\sqrt{n}$) exists.

######  Theorem A.1.

For every integer $1\leq t\leq n$, Algorithm 1 is $O(\log(t+1)+\min\\{\log
n,\max\\{1,\log{\frac{n\eta^{(t)}_{\infty}}{\operatorname{OPT}}}\\}\\})$-competitive.

###### Proof sketch..

Let $\Gamma=(\gamma_{1},\gamma_{2},\ldots,\gamma_{t-1})$ be indices of the
$t-1$ largest prediction error
$d(f_{x_{\gamma}}^{\mathrm{pred}},f_{x_{\gamma}}^{\mathrm{opt}})$. The high
level idea is to break the dataset $X$ into a good part
$X_{G}:=\\{x_{i}:i\in[n]\backslash\Gamma\\}$ and a bad part
$X_{B}:=\\{x_{i}:i\in\Gamma\\}$ according to whether or not the prediction is
within the outlier, and we argue that the expected cost of ALG on $X_{G}$ is
$O(\frac{n\eta^{(t)}_{\infty}}{\operatorname{OPT}})$ times larger than that in
OPT, and show the expected cost on $X_{B}$ is $O(\log(t+1))$ times.

For the good part $X_{G}$, we let $X_{-}(f^{*}):=X(f^{*})\backslash\Gamma$ and
apply a similar analysis as in the proof of Lemma 3.5 to show that

$\displaystyle E\left[\sum_{x\in
X_{-}(f^{*})}\operatorname{cost}(x)\right]\leq
O\left(\max\left\\{1,\log\frac{n\eta_{\infty}^{(t)}}{\operatorname{OPT}}\right\\}\right)\left(w(f^{*})+\sum_{x\in
X_{-}(f^{*})}d(x,f^{*})\right).$

For the bad part $X_{B}$, we assume all predictions for points in $X_{B}$ are
of infinite error (which could only increase the cost of the algorithm), and
let $X_{+}(f^{*}):=X(f^{*})\cap\Gamma$. Then this lies in the case of Section
3.2, where $7\eta_{\infty}>4w(f^{*})$, which essentially means the prediction
is almost useless and the whole proof reverts to pure Meyerson’s algorithm.
Combine the arguments from Section 3.2 and the analysis for the short distance
stage, we have

$\displaystyle E\left[\sum_{x\in
X_{+}(f^{*})}\operatorname{cost}(x)\right]\leq
O(\log(t+1))\left(w(f^{*})+\sum_{x\in X_{+}(f^{*})}d(x,f^{*})\right).$

We finish the proof by combining the bound for the two parts. ∎