Online Facility Location with Predictions
Authors: Shaofeng H.-C. Jiang
Erzhi Liu
You Lyu
Zhihao Gavin Tang
Yubo Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: online algorithms
facility location
prediction
learning-augmented

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}{\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
Shaofeng H.-C. Jiang
Erzhi Liu
Peking University
Shanghai Jiao Tong University
Email: shaofeng, iangepku.edu.com
Email: lezdzhu jtu. edu. cn.
You Lyu
Zhihao Gavin Tang
Shanghai Jiao Tong University
Shanghai University of Finance and Economics Email: tang zh d ha o@ma i 11 shufe. edu.cn.
Email: vergi 1 @s wtw.ttu.uuuuu....... edu.cn
Yubo Zhang
Peking University
Email: 2hangyabe18@pku. edu.
ABSTRACT
We provide nearly optimal algorithms for online facility location (OFL) with pre- dictions. In OFL, demand points arrive in order and the algorithm must irrevo- cably 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 pe
given for each demand point a natural prediction fpired which is supposed to be the facility fore that serves 2; in the offline optimal solution.
Our main result is an Omin (log OPT log ) competitivee algorithm where Toc is the maximum prediction error (i.e., the distance between fpred and fopt). Our algorithm overcomes the fundamental 2
log 1 lower bound of OFL (without predictions) when 7/so is small, and it still maintains O(log n.) ratio even when Tho is unbounded. Furthermore, our theoretical analysis is supported by empirical evaluations for the tradeoffs between 1/oc and the competitive ratio various real datasets of different types.
INTRODUCTION
We study the online facility location (OFL) problem with predictions. In OFL, given metric space (X', d), a ground set D C of demand points, a ground set F C X of facilities, and an opening cost function the online algorithm must irrevocably assign I; to some open facility, denoted as f. upon its arrival, and open facility cannot be closed. The goal is minimize the following objective
F I.,. the input is a sequence of demand points X := (æ),..., Ix,) C D, and
Σw() + Σ Mai,fe), FEF
2.EX
where F is the set of open facilities.
Facility location 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), dis- tribution system design (Klose & Drexl, 2005), healthcare (Ahmadi-Javid et al., 2017), and more be found in surveys (Drezner & Hamacher, 2002: Laporte et al., 2019). Its on- line variant, OFL, was also extensively studied and well understood. The state the art is an loga >ccopetitivee deterministic algorithm proposed by Fotakis (2008), and the same work O log log
applications
shows this ratio is tight.
We explore whether not the presence of certain natural predictions could help to bypass the barrier. Specifically, consider the setting where each demand point 2; receives
O
log n
log log

---

predicted facility fa that is supposed be z,'s assigned facility in the (offline) optimal solu- tion. This prediction is very natural, and it could often be easily obtained in practice. For instance, if the dataset is generated from latent distribution, then predictions may be obtained by analyz- ing 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. Previ- ously, predictions of a similar flavor were also considered for other online problems, such as online caching (Rohatgi, 2020; Lykouris & Vassilvitskii, 2021), ski rental (Purohit al., 2018; Gollapudi & Panigrahi, 2019) and online revenue maximization (Medina & Vassilvitskii, 2017).
1.1
OUR RESULTS
Our main result is near-optimal online algorithm that offers smooth tradeoff between the pre- diction error and the competitive ratio. In particular, our algorithm is ((1)-competitivv when the predictions
perfectly accurate, i.e., f2red is the nearest neighbor of x; in the optimal solution for every 1 S i S n. On the other hand, even when the predictions are completely wrong, our algorithm still remains (log n) competiiiie.. As in the literature of online algorithms with predictions, our algorithm does not rely on the knowledge of the prediction error 1/
Theorem 1.1. There exists an O n. max log OPT comppetiiee algorithm for the OFL with predictions, where The maxigiçn d( M[[pred, sopt) measures the maximum prediction error, and fore is the nearest neighhor of x4 from the offline optimal solution OPT!
Indeed, also interpret our result under the robustness-consistenn 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, We also remark that our robustness bound
framework which is widely
our algorithm is ((1)-consistent and nearly matches the lower bound for the OFL without predictions.
One might wonder whether or not makes sense to consider a related error measure, 7i E d(ffreed fopt), ). which is the total error of predictions. Our lower bound result (Theorem 1.2) shows that a small ?n is not helpful, and the dependence of 1/ in our upper bound is fundamental (see Section F for a more detailed explanation). The lower bound also asserts that our algorithm is nearly tight in the dependence 1/x-
Theorem 1.2. Consider OFL with predictions with uniform opening cost of For every Teo (0, 11. there exists class of inputs, such that no (randomized) online algorithm is of log mooe competitive, even when 1/1 O(1).
Tog log
As suggested by an anonymous reviewer, it might be possible to make the error measure T/oo more "robust" by taking "outliers" into account. A more detailed discussion on this can be found in Section G.
Empirical evaluation. We simulate our algorithm on both Euclidean and graph (shortest-path) datasets, and we measure the tradeoff between Vocc and the empirical competitive ratio, by generat- ing random predictions whose 7 is controlled to be around some target value. We compare with two baselines, the O(log (i)loggn-coomtttttii diction at all, and naive algorithm that always trusts the prediction. Our algorithm significantly outperforms Meyerson's 's algorithm when 7/ + O, and is still comparable to Meyerson's 's algorithm when 17co is large where the follow-predie cello-predintion baseline suffers a huge error.
algorithm by Meyerson (2001) which do not use the pre-
We observe that our lead is even more significant datasets with non- con-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 Th only concerns the connection costs without taking the opening cost into consideration (i.e., it could be that a small ne 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- con-uniform opening cost setting.
When the context is clear, we also use OPT to denote the optimal solution.
2

---

Finally, we test our algorithm along with very simple predictor that does not any sophisticated ML techniques or specific features of the dataset, and it turns out that such a simple predictor al- ready achieves 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 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(-), 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 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 OPT) ) Olog "M]0e) log(emo)
while the ratio in Fotakis et al. (2021a) is log(err 'og(em)))) where erto = 1TJoce/ /w, emr = m n1/w and w the uniform opening cost. Our ratio comparable to theirs when ?h relatively small. However, theirs seems to be better when 7) is large, and in particular, it claimed in Fotakis et al. (2021a) that the ratio becomes constant when eIT & emty Unfortunately, we think this claim contradicts with our lower bound (Theorem 1.2) which essentially asserts that 7/2 (n= is not helpful for the ratio. Moreover, when 7/2 is large, we find their ratio is actually not well-defined since the denominator log(erri log(erro)) is negative. Therefore, we believe there might be some unstated technical assumptions, or there are technical issues remaining to be fixed, when v/1 is large.
Another independent work by Panconesi al. (2021) considers a different model of predictions which is not directly comparable to ours. Upon the arrival of i-th demand point, a set of multiple predictions S; is provided, each suggesting a list of facilities be opened. Their algorithm achieves a cost of ( S:I) OPT(U, S,)) where OPT(U, is the optimal using only facilities in U,S, and the algorithm also has a worst-case ratio of O log in case the predictions are inac- curate. Similar to the abovemention Fotakis et al. (2021a) result, this result only works for uniform opening cost while ours work for arbitrary opening costs.
1.2 TECHNICAL. OVERVIEW
Since aim for worst-case (i.e,, when the predictions are inaccurate) O(logn) ratio, our algo- rithm is based on an Oloog ((logn)-come -no-mptttiiivve algorithm (that does not use predictions) by Meyerson (2001), and we design 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 '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 F, such that for every facility f" opened in ОPT, F' contains facility f that of distance Tooo to f", then Meyerson's 's algorithm is Olog OPT additional facilities so that for each facility in OPT, the algorithm would soon open a close enough facility.
wis )-copetiitiee To this end, our Prediction step aims to open
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 facility, we further open 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 reward, when the prediction error 1ooo 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-unin non-uniform case. Specifically, opening facility exactly at the predicted location could be prohibitively expensive 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.
3

---

The design of the Prediction step for the non- 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 f that is (17cc) apart to the cor- responding facility in OPT, and that the total cost until f is opened is merely O(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 (hecause of the doubling opening cost). Once open this f. subsequent runs of Meyerson steps would be O(log OPT OPT)
nis ccompetitive.
1.3 RELATED WORK
OFL is introduced by Meyerson (2001), where a randomized algorithm that achieves competitive ratios of ((1) and Ologn) are obtained in the setting of random arrival order and adversarial arrival order, respectively. Later, Fotakis (2008) gave a lower bound of S2( Tog log and proposed a deterministic algorithm matching the lower bound. In the same paper, Fotakis also claimed that an lug )) competitive ratio in the improved analysis of Meyerson's 's algorithm actually yields an O log
setting of adversarial order. Apart from this classical OFL, other variants of are studied as well. Divéki & Imreh (2011) and Bamas al. (2020b) considered the dynamic variant, in which open facility can be reassigned. Another variant, OFL with evolving metrics, was studied by Eisenstat 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 formal definition of consistency and robustness. For the ski-rental problem, Purohit al. (2018) gave an algorithm with a hyper parameter to maintain the balance of consistency and robustness. They also considered non-clairvoyant scheduling on single machine. Gollapudi & Panigrahi (2019) designed an algorithm using multiple predictors to achieve low prediction error. Recently, Wei & Zhang (2020) showed tight pbbustness-consistenn trade- off for the ski-rental problem. For the caching problem, Lykouris & Vassilvitskii (2021) adapted Marker algorithm to use predictions. Following this work, Rohatgi (2020) provided 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 maximiza- tion problem and Bamas 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 al. (2021) studied online matching problems with predictions in the constrained adversary frame- work. Azar et al. (2021) and Lattanzi et al. (2020) considered flow time scheduling and online load balancing, respectively, in settings with error- prror-prone predictions.
PRELIMINARIES
Recall that we assume underlying metric space (X, d). For C X. E X,, define d(x, S) We normalize the opening cost function w
minyes d(x, v). For an integer t, let [t] := 21, 1). 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,
assume the domain of w is E } for some L. Further, we use G3 to denote the set of facilities whose opening cost 1 1 (2'-1
most 2 i.e. Gx (ʃ
F w(()) < 2*-1), 1), v1 < & < L. Observe that Go 0.
4

---

Algorithm Prediction-auggeenii Meyerson
F, Fp are the set of all open facilities and those opened by PRED 2: for arriving demand point a E X and its associated fpred do
1: initialize F < D, Fp +
3: cost (x) MEY (a:)
4: PRED (fpred costM(z))
5: procedure (EY(x)
6: for [L] do
7:
fe - arg minsEFUG, d(z,
8:
6g + d(x,
9:
P& < (ōg-1 6x)/2", where 6, = d(x,
let sk E Di=xP0 Ps for k E [L]
11:
sample ~ Uni 10, 1]. and let E [L] be the index such that r E 84)
if' such exists then
13:
F FU
D open facility at fa
14:
connect the nearest neighbor in F D i does not exist, simply return d(x; F)
15:
return d(x, F) + w(i)
16:
procedure PRED(Sered .g)
17:
repeat
18:
r+ [d(ffrodd FP)
Sopen + arg arg min f:d(se -DSr ((f) break ties by picking the closest facility fpred if q 2 wl (o(Spp))) then F FU fopens Fp Fp Sopen
20:
21:
open facility Sopen
22:
g 4- x-
23:
until @ < ((open)
24:
open facility at Sopen with probability "(Fopon) and update F, Fp
OUR ALGORITHM: PREDICTION-AUGMENTT 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, first run the Meyerson algorithm Meyerson (2001), and let costM(2 be the cost from the Meyerson step. Roughly, for a demand point x, the Meyerson algorithm first finds for each 2 1, facility fa which is the nearest to x, among facilities of opening cost at most 2 and those have been opened, and let 6% d(x,, fx). Then. open random facility from {fa such that fa picked with probability (ōx-1
bx)/2* For technical reasons, we do not normalize Σx Pk, and we simply truncate if Στ Pk 1. Next, we pass the cost incurred in the Meyerson step (which is random) as the budget g to the Prediction step, and the Prediction step would use this budget to open series of facilities through the repeat-until loop. Specifically, for each iteration this loop, a facility is to be opened around distance r to the prediction, where 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.
ny Theorem 3.1. Prediction auggeetteddd Meyerson is O(min n, max log OPT 1)) competirive.
Calibrating predictions. Recall that 7o0 = max d( fpred d(fprred popt) can be unbounded. We show how to "calibrate" the bad predictions so that T/sc = (OPT)) Specifically, when a demand point arrives, we compute S' := arg minner(d(xr, + w(f)). and we calibrate fpred by letting fpred f% if d(x,, fgrod) > 2d(x, f() wwff).
We show the calibrated predictions satisfy 7oo ((PT)) Indeed, for every demand point x, fopt) < d(x, f2) + d(x,, fopt) < 2d(x, f') w(f)) < O(OPT), where the second to last inequality follows from the optimality (i.e., the connection cost d(æ, fopt) has to be smaller than the cost of first opening f' then connecting to f)). Note that, if To0 O(OPT) then OPT O(n), hence it suffices to prove a single bound (mmxx (1, log 2p 1) for Theorem 3.1 (i.c., ignoring the outer min).
5

---

Algorithm analysis. Let Fopt be the set of open facilities in the optimal solution. We examine each f E Fopt and its corresponding demand points separately, i.c. 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 I, let F(z) be the set of open facilities right after the arrival of request æ, F(xx) be the set open facilities right before the arrival of x, and F(x)= = F(x) \ F(x) be the set of the newly-open facilities on the arrival of æ. Moreover, let Fa)()), (a( be a partition of F(x), corresponding to the facilities opened by MEY and Pred, respectively. Let (x),), Fa((),, Fp(x), (x) be defined similarly.
(x))(())) (z, (F) U FF(x)) be the the total cost from MEY step. Let costp(x) = w (FF((z)) be the cost from PRED step. Let cost(z) = (() costp(x) (I:) be the total cost of a.
Definition 3.3 (Costs). Let cost
Recall that after the MEY step, assign total budget of (os to the PRED step. That is, the expected cost from the PRED step 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. [[cos(((x))) = E[costM<x))-
Proof. Consider the expected cost from the PRED step. Given arbitrary Fp. there only one random event from the algorithm and it is straightforward to that the expected cost equals q- Notice that our algorithm assigns a total budget of = cost Thus, E[cost(xx) = EEcoosta ( cost (3:) 2 TE| cost (-:)].
Therefore, we are left to analyze the total expected cost from the MEY step. The following lemma the most crucial our analysis. Before continuing the proof of the lemma, we explain how concludes the proof of our main theorem.
Lemma 3.5. For every facility f E Fope, we have
EfcostM(x)) s 50 (max (1, To/ -EX(""
Σ
OPT)) }) (m(()+
()
E
d(z.f)) +0
[X(')) n
OPT
=EX(
Proof of Theorem 3.1. Summing up the equation of Lemma 3.5 for every f Fopt. have
B[ALG]
Σ
[x)) 2
Σ E(costM(x)) = Σ Σ
E(costM(x))
sex
Fopt =EX(1*)
Σ f Fopss
o (max 1, log
((([++ Σ
d(c,))) +0
[X(F') OPT)
OPT
=EX(M)
0 max 1, log
OPT ))
ОPT, 1i//00
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 77 = 0.
3.1 PROOF OF LEMMA 3.5
Fix an arbitrary f E Fope- Let 6 be the integer such that w(f*)= -1 equivalently f Ge Let X(f*) {#1, T2. ,m be listed according to their arrival order. We remark that there can be other demand points arriving between z; and Ti+1, but they must be connected to other facilities the optimal solution. Let é, be the index such that d(f". F(r:)) E [26 2,)). l, can be negative and if d(f", F(x:)) 0, let f; -c. Observe that F(f+,F(x;) and l; are non-increasing in i. Let T be the largest integer i with F(x))) > min(77700 Aw(f)) Note that T is a random variable. We refer to the demand sequence before x, the long- distance stage and the sequence after x, as the short-distance stage. In this section, we focus on the case when 71000 & 4w(("). The proof for the other case is very similar and can be found in Section E.

---

Long-distance stage. We start with bounding the total cost in the cong-distance stage. Intuitively, our procedure PRED would quickly build a facility that is close to f within distance of ( since it is guaranteed that for each demand point z,, the distance between f* and its corresponding prediction sered is at most T/oc- Formally, we prove the following statements.
Lemma 3.6. E Dier (x:) 2w((*)
Proof. The proof can be found in Section
Lemma 3.7. ((costt((xx)) & ( + + ((x;
Proof. The proof can be found in Section B.
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, with > т. The analysis of this part is conceptually similar to part of the analysis of Meyerson's 's algorithm. However, ours is more refined in that it utilizes the already opened facility that is near f" to get an improved Ollog OPT) ratio instead of (log n.). Moreover, Meyerson did not provide the full detail of this analysis, and our complete self-contained proof fills this gap.
By the definition of T, have d(ʃ" F(x:)) T1% for such т. For integer L, let It
& = -). Then for such that 2 > min(7 4vx([*)), we have Ie = 0. Let be the integer that OPT [26-1,29 22), and let ? be the integer such that min Awo(f)) [2 2 We partition all demand points with > т into groups Iee-1, 17 according to L,, where Ise-1 Upse-1 Lt.
Lemma 3.8. E [Eerge-,
< 2|XI/" OPT.
n
Proof. The proof can be found in Section C.
Lemma 3.9. For every & E [.. E Diee, costM((::)) < 18 EiEE, d(z,f") + 32wl(**)
Proof. The proof can be found in Section D.
Proof of Lemma 3.5. We conclude Lemma 3.5 by combining Lemma 3.6, 3.8, and 3.9.
coost (x;)]
Σ
(as)
+ E|costM (#+))
KE ml
iE(T-1] 1]
E
costM (2x))
+
Σ
E (c:)
lm
Liete
iETse
< 2w(s")
2w(s*) + > ((xz,
i
2[x(f*)
+ Σ
18 Σ
d(x,, f*) (f)
OPP
l=g
IET
2)x(f*))
S -0 O
Σ
d(rs, f*) +w((t)
OPT
n
(e(m)
0 maxx
1o
pp 1)
Σ
d(z d( ()+ +0
[X(]*) OPT
n
te ml]

---

Table 1: Specifications of datasets
dataset
type
size
# of dimensionneddes
non-uniform
Twitter
Euclidean
30k
dimension =
no
Adult
Euclidean
32k
# dimension = 6
no
US-PG
Graph
4.9k
edges = 6.66
no
Non-Uni Uni
Euclidean
4.8k
dimension =2 yes
4 EXPERIMENTS
We validate our online algorithms on various datasets of different types. In particular, we consider three Euclidean data sets, a) Twitter (Chan al.), b) Adult (Dua & Graff, 2017), and e) Non- Uni (Cebecauer & Buzna, 2018) which are datasets consisting of numeric features in Rd and the distance is measured by l2. and one graph dataset, US-PG (Rossi Ahmed, 2015) which represents US power grid in graph, where the points are vertices in graph and the distance is measured by the shortest path distance. The opening cost is non-uniform 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; Johen-Addal et al., 2019). A summary of the specification of datasets can be found in Table 1.
Non-Uni dataset, while uniform in
Tradeoff between Tic and empirical competitive ratio. Our first experiment aims to measure the tradeoff between 7/2o and the empirical competitive ratio of algorithm, and we compare against two "extreme" baselines, a) the vanilla Meyerson's s algorithm without using predictions which we call MEYERSON, and naive algorithm that always follows the prediction which we call FOLLOW-PREDICT Intuitively, a simultaneously consistent and robust online algorithm should perform similarly the comparable to MEYERSON when the prediction is of low quality.
baseline when the prediction is nearly perfect, while
Since is NP-hard 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 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 Too and demand point we pick a random facility f E F such that /2 2 I
Ft) S Tooo as the prediction, where F the point in F that is closest to The empirical competitive ratio is evaluated for every baselines as well as our algorithm on top of every dataset, subject to various values of 77.
All experiments 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 we plot for every dataset line-plot for all baselines and our algorithm, whose x-axis is Vic and y-axis is the empirical competitive ratio. Here, the scale x-axis is different since the scale of the dataset. From Figure/ 1, it be seen that algorithm
Ns is dependent performs consistently better than MEYERSON when The is relatively small, and it has comparable performance to MEYERSON when Tooo is so large that the HOLLLO--PREDIE baseline loses control of the competitive ratio. For instance, in the Twitter dataset, our algorithm performs better than MEYERSON when 7oc S 2, and when Toxc becomes larger, our algorithm performs almost the same with MEYERSON while the ratio of FOLLOW-PREDICT baseline increases rapidly.
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 tricky to use since predictions at "good" locations could have large opening costs. In particular, our algorithm does good job to find "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 training set, and evalute its performance predictor has access to a training set T. Initially, the predictor runs the 3-approxemate MP algorithm on the training set T' to obtain solution F*. Then when demand points from the dataset (i.e.,
datasets. We assume the
8

---

Moyersoe
Meyerson
2.0
Our
Ours
Folow-Prdd
Compettire Radio
1.6
2.6
Competiivve
1.
1.44
1.0
100
Parameter Ybu
Parameter Toe
Twitter dataset
Adult dataset
Meyerson
Follow Predict
FolizePredict
Dur
Ous
Competitivn Ratio
10
2.6-
Competitve
7.4
1.2
1.0
0.000 nuiz auoos nx006 n.tos nudin 0.022 0.014 0.066 Ervor Paramoter
Error Parameter T/u
US-PG dataset
Non-Uni datasct
Figure 1: The tradeoff between prediction error Tho and empirical competitive ratio over four datasets: Twitter, Adult, US-GD and Non-Uni.
Table Empirical competitive ratio evaluation for the simple predictor
dataset
Meyerson
Follow-Predie
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
test set) X arrives, the predictor periodically reruns the MP algorithm, on the union of and the already-seen test data X' C X, and update f* For 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 comparable to Meyer- son's algorithm. Moveover, when combining with this predictor, algorithm outperforms both basclines, especially on the Non-Uni dataset where the improvement 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 domain-specifee signals/features from the data points (which are however commonly used designing predictors), already achieves reasonable performance. Hence, we expect to see even better result if carefully engineered predictor is employed.

---

ACKNOWLEDGMENTS
This work supported by Science and Technology Innovation 2030 "New Generation of Artifi- cial Intelligence" Major Project No.22018AA010000 Program for Innovative Research Team of Shanghai University of Finance and Economies (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. 2021 YFA 1000900. Zhihao Gavin Tang is partially supported by Huawei Theory Lab. We thank all anonymous reviewers for their insightful comments.
REFERENCES
Amir Ahmadi-Javid, Pardis Seyedi, and Siddhartha S. Syam. A survey of healthcare facility location. Comput. Oper. Res., 79:223-263 2017.
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online match- ing problems with machine learned advice. NeurIPS, 2020.
Yossi Azar, Stefano Leonardi, and Noam Touitou, Flow time scheduling with uncertain processing time. In STOC, pp. 1070-1080, 2021.
Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In NeurIPS, 2020a.
Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. In NeurlPS, 2020b.
Matej Cebecauer and L'uboš Buzna. Large-scale test data set for location problems. Data in brief, 17:267-274, 2018.
T.-H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dynamic k-center clesttrrnn WwW, pp. 579- 587. ACM, 2018.
Hubert Chan, Guerqin, and M. Sozio. Twitter data set. BeGBBBBR4vvKKKKKeeexxxx center.
URL httth://ggtthttti com/
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In NIPS, pp. 5029-5037 2017.
Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In NeurlPS, pp. 3250-3260, 2019.
Gabriella Divéki and Csanád Imreh. Online facility location with facility movements. Central Fur. J. Oper. Res., 19(2):19-2000 2011.
Zvi Drezner and Horst W. Hamacher. Facility location applications and theory. Springer, 2002.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL ics. www.uciiuuu.. mardu//m//attaae
/adult.
Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In EC, pp. 409-429, 2021.
David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In ICALP, volume 8573, pp. 459-470, 2014.
Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008.
Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris. Learning augmented online facility location. CoRR, abs/2107.082777 2021a.
Dimitris Fotakis, Loukas Kavouras, and Lydia Zakynthinou. Online facility location in evolving metrics. Algorithms, 14(3):73, 2021b. 2021b.
10

---

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.
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.
Andreas Klose and Andreas Drexl. Facility location models for distribution system design. Eur. J. Oper. Res., 162(1):4-29, 2005.
Gilbert Laporte, Stefan Nickel, and Francisco Saldanha da Gama. Location science. Springer, 2019.
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In SODA, pp. 1859-1877, 2020.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive eaching with machine learned advice. J. ACM, 68(4):24:1-24:25, 2021.
Andres Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid pre- dictions. In NIPS, pp. 1858-1866, 2017.
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-41,, 2009.
Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. In FOCS, pp. 339-348. IEEE Computer Society, 2000.
Adam Meyerson. Online facility location. In FOCS, pp. 426 431. IEEE Computer Society, 2001.
Alessandro Panconesi, Flavio Chierichetti, Giuseppe Re, Matteo Almanza, and Silvio Lattanzi. On- line facility location with multiple advice. In NeurlPS 2021, 2021.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In NewrlPS, pp. 9684-9693, 2018
Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In SODA, pp. 1834-1845. SIAM, 2020.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL / http:://ettwrrkrppiiiioo com.
Alexander Wei and Fred Zhang. Optimal robustness-connsisencyy trade-offs for online algorithms. NeurlPS, 2020.
A PROOF OF LEMMA 3.6
Lemma A.1 (Restatement of Lemma 3.6). E EEir (I:)M < 2w(f*).
be the facilities opened by the PRED steps on the arrivals of all (æz)iers and are listed according their opening order. Observe that the budget that is assigned to the PRED step cost (I:), and the expected opening cost of each PRED step equals its budget. By
Proof. Let (2.199......
definition of G. we have |Etey cost (x:)) E [xetey w(gh)
Next, prove that the opening costs of gk² 's always strictly increasing. For each it - 1]. suppose It is opened on the arrival of demand and ge+1 is opened on the arrival of demand y. Let F denote the set of all open facilities right before gk+1 is opened. Let

---

= arg min f=dls f)S 3 .gw) w(f), must have w(gk+1) 2 w(f), since 9h+1 arg min f .1/ d( w(f) and that di ((spred, F) s d(spred ga). Moreover,
1
d(,,2 (2 < 1 + d( d(s sprod) S
5 _d([prrn :gk) + 21/s0
2
1 2 (d(sered ,g.) + d( d(fer [ ((
fpred) + 21o S _d(S .gk) + 37/30 < d(sfrrdd gb).
Here, the second and fourth inequalities ( I 2n since both z.y y X())). The last inequality follows from the fact that d(spred ,gk) 2 d(gr, 1*) d(pered , (²) TTp Tee 61/ by the definition of
the fact that ((fprod.pprd) I d(fpred f*) +
Consider the moment when open gk. the fact that do not open facility implies that w(g)) w(f). Therefore, w(gs) < w(f) S w((k-1). Recall that the opening cost of each facility a power 2. We have that ΣxE(q) w(gh) 2ur(ge).
Finally, we prove that the opening cost w(g+) is at most w(f"). Consider the moment when gr. open, let x be the corresponding demand point. Notice that
C(J",Jered S Tho "(" F(x)) z " Fr(x)),
((x))
2
by the definition of r. However, we open instead of f on Line 20 of our algorithm. It must be the case that w(f*) w(g:).
To conclude the proof, we have ΣxEM w(g)) S 2w(g:) S 2w(
B PROOF OF LEMMA 3.7
Lemma B.1 (Restatement of Lemma 3.7). M S + d(r;;
Proof. We bound the opening cost and connection cost separately.
Opening cost. By the algorithm, we know for every 1 i m,
E w/ ( (Fa((())))))))) > w0 (F))
S
Σ
0 82
2 = dr- S s(ri,
2
Hence, using the fact that at most one facility opened by Meyerson step for each demand,
Blw( ((o(Assx7))) s E
max sEFaa(em))
w(n)
s ww(+)+ +E
Σ
w(f)
I w(())
Σ d()
This finishes the analysis for the opening cost.
Connection cost. We claim that d(z,, F(x+)) & w(f') + d(x,: f*) (with probability 1).
Let 60, .1,...,or be defined as in algorithm. We assume 6g d(ær, F(xz)) w(f") + [(x+ff") as otherwise the claim holds immediately. Let k == max(k: 6x > w({r) + d(xTr:))) Then
Pr[d(z,,FFz, w(f") d(zr.f")
Σ #=++1
8-1-8 min
Σ 1=t+1
8 8: 11
(6 10x-00 -ō-
1) 1.
min
min
2
2
26
Therefore, E[costaa (x+)) = E[w(FM((z)) + E[d(f" F(x,)) $ 2w(f*) + +2 -m d(z f*),
which concludes the proof.
12

---

C PROOF OF LEMMA 3.8
Lemma C.1 (Restatement of Lemma 3.8). E
costM (2:) Eieter
2|x(f)) OPT.
Proof. For i E I-g- we have that its connection cost d(x,, F(x:)) S d(a,, F(z;)) S 2 = OPT, Let da, ò1,...y ......,, òr, and fi....: fr defined as in our algorithm upon x; 's arrival. Then, its nn expected opening cost in the MEY step equals
E w ((F((()))))
Σ Pr KE[L]
(a((z)) [fil]] w(f+)) S
Σ
min (pt: 1)- 22
kE[L]
min (
8ū
80
OPT
Σ kE[T]]
2
Σ
<
2h
2
2n
kE
To sum up.
E
Σ
(z4)
SE
Σ (d(zn ((Br((z)))
Σ
3
OPT
2n
iElee-1
iEIce-1
ielce-1
2[x(
OPT.
D PROOF OF LEMMA 3.9
Lemma D.1 (Restatement of 3.9). For every l L.
E
Σ LiE4
costxa(x)) (x))
S 18 Σ
REL,
Proof. Recall that we relabeled and restricted the indices of points in X to X(f*) faI...... Fm } However, in this proof, we also need to talk about the other points in the original data set (that do not belong to X())). Hence, to avoid confusions, we rewrite X (Vi,..., yn J (so yı, ,...... Un. the demand points order), and we define a [m] + [m] that maps elements Tj E x(f*) to its identity y1 X, i... o(j)
For i E [n). let
(M)) none
(M)) 0
2/
otherwise
and define zf similarly. Since the MEY step opens at most one facility, a! either singleton or "none". Finally, define 2 == 2 Uz.".
Define Ti minfi [n] 22M none and d(f", MM) 26-1), we have
E LIELe
cost (x:)) - 18d(a,, (+) =
(costm(y:) 18d(,, 18dgy, (1)
Next, we prove a stronger version by induction, and the induction hypothesis goes as follows. For every j E [n]].
Tt (cost (3:) 18d(y,, (() |& &
E
32w(f*),
where E = ( 2,). Clearly, applying this with j = 1 implics (1), hence it suffices to prove this hypothesis.
13

---

Base The base case is j n, and would do backward induction on j. Since condition on E--1. the variables óo.... oy in the MEY step of Bj. as well as wether or not j E (lt), fixed. Hence,
L Σ
1
6
E[costm( ( S d(ys, F(U)))
+
S 2d(y5: F(u))).
2
This implies
(costa((1)) - 18d(y;. f() E
[|(costx (Hn) 18d(yn: f 1)) (n o(L))) En-1]
2d(yn= F Flyn)) 18d(yn Inea(te)
2d(yn: F(yn)) 2d(yus 1*) InEO()))
2d( (ynn) 1*) InEo(1e)
s z 2 S <Ow((f))..
Inductive step. Next, assume the hypothesis holds for + 1.j + 2...., n, and we would prove the hypothesis for j. We proceed with the following case analysis.
Case 1: E (Iz). We do a conditional expectation argument, and we have
E
(cost 18d(u,, (i) 1
Σ
Pr
M
| (costm(()) - ()) E5-1, 2p
2) 2
(f*)
where the second step follows by induction hypothesis.
Case 2: Te and 8d(y), f*) d(s", F(y))) We have
d(y;, F(y))) S d(y;, f*) + d(f", F(y))) < 9d(y,, f*).
Hence E|costM (U;) - 18d(y, f]] - 0, and the hypothesis follows from similar argument as in Case
Case 3: E Le, and 8d(y;, f*) < d(f", F(,,)) We have
de- S d'y, f*) < d(f", F(y,)) s 24-3.
Let { d([(())) 2t-1] fnone). Let l: min(k' dz S 22-2). Then Vi 2 k
d(Si,f") S d(y,, d(yj. 1n) < 26-11
Pr[m Sjll 2 Pr [>M
M $ D Ej-1] 2 Pr is open for some i 2 k 1 E
8 6
min
Σ Pii 1
min
Σ
1
i2k
[5k-1 de.
2
28-3
1 > min (2-33-111)
min
min
20
2
dp
Elcostm (1;) E
16w(f*)
32w(f*)
14

---

where the second last inequality follows from du d(ys, F(y)) s 2 and w(f*) 2f"-1. Thus,
LHS [[costM Eg-1]
Pr(z = 1 E
(costM(())) - 18d( E--1; 1,
LED =
< Pr M $ D E--1] (2w(f²) + Pr
[2] M
E Eg-1] 32w(f*)
s (fw
where the second step follows by induction hypothesis. In summary, we have
7e
(costM fo) (
En-1 $ 32w(f")
E PROOF OF LEMMA 3.5: WHEN 7h0 > 4w
The proof is mostly the same 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 т, L. and l. 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 71 < 4w)(") which does work in the current case. We provide Lemma E.2 in replacement of Lemma 3.6, which offers a slightly different bound but it still suffices for Lemma 3.5.
Lemma E.1. For every < T. d(x,, f*) 2 w(f")
Proof. We prove the statement by contradiction. Suppose d(x;, f*) w(f*). Let Sa, ō1. ........ 6w be defined as in our algorithm. Then, we have
d = d(z, F(x:)) F(x)) ((f.)))d((f,)))))) d(f d(a,, -(a.)) > 3w(f")
where the last inequality follows from the definition of that d(s", F(x,)) > Aw(s"). Let m 6₂ < (w(f*)} We have ls 2 1. We prove that facility within a distance of (f()") from Iy must be open at this step.
Pr [d(2,, F(x,)) $ 3wo(f)) 2 Pr Ify is opened for some j 2 k]
8 8 81
min
Σ Pk:
2 min
Σ
2
j2k
j=k
0 de 2
1) min
(w((f*) - w w0(()
min
20
where the last inequality uses the fact that 85- S d(zr, f*) S w(f*). Consequently,
d(" (x++1) S d(s", F(x:)) < d(a,, F(x:)) + d(z;, f*) < 4w(l"),
which contradicts the definition of T.
Lemma F.2. FF [ve(t)) (x;) S 6 [()) + 4 w((r).
Proof. On the arrival of x; for each i E [r], let on S1...., dr be defined as in our algorithm. We first study the connecting cost of request I,, We have
das, F(x))) < max (d(c,, ((x,) da, F(x:))) = max (80, d(r, ((x:)))
15

---

We prove this value is most d(z,, +ww(f") Suppose dg d( f*) 2w(f") as otherwise the statement holds. Recall that 6, is non-inonennn -nnnincrrassn let tt = min 6g I d( f() + 2w)))) By the definition of k. we have that
Pr [d(,;; F(x))) S d( f*) + 2w( (f) 2 Pr[fy is opened for some j j k]
Σ --1 -J -5 j2k
.1 2 min /dk-1 de.
min
Σ j2k
Ps.
min
-11
d( (*) + +2((f*) - de - 1) min
(w(f*) 22-11
min
2
To sum up. we have shown that the connecting cost d(r;, F(2,)) S d(I,, f*) + 2w(f*).
Next, we study the expected opening cost [[w(F(z;))). We have
[8/1- ,1) 20-1
Biw ([w(F(z)))
Σ
Pr
F(x,)
[f}]] (((f)) - Σ
min
21
SE(L]
jE(L]
6--1- - 6g 2
1
2
+
2d00 < 20( ) + d(ss,
2
2
J58
By Lemma 1. we conclude the proof of the statement:
E
Σ
(x;)
E
d(ri, F(r.)) + w/ =(((x:)))
EE
EE(T]
E
(2d( f*) 11 4w(ff))
SE[T]
< 6
d(wi, 1*)) + (2d (*) 4w ((()
KT
6E
Σ d(wi, (*) 4wi(S*)
/E|T]
F LOWER BOUND
In the classical online facility location problem, tight lower bound of O log log log x
is established by Fotakis (2008), even for the special case when the facility cost is uniform and the metric space is a binary bierarchically well-separated tree (HST). We extend their construction to the setting with predictions, proving that when the predictions are not precise (i.e. Tex 0), achieving a competitive ratio of of log wares
is impossible.
Tog log n
Theorem F.1. Consider OFL with predictions with uniform opening cost of 1. For every Tiso (0, 1), there exists a class of inputs, such that no (randomized) online algorithm of log Wet competitive, even when =
log log
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 7 < 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 7/5o = 0(1).
Without the normalization, theorem implies impossibility result of of facility location with predictions.
log o for online
log log
16

---

Moreover, recall the definition of total prediction error 771 = ='==1 di ((fPred fo.t), which is at least max; dl [ ". Our theorem states that even when the total error 7h is constant times larger than the opening cost of I, there is no hope for a good algorithm. Note that our bound above holds for any constant value of Toc. As an implication, our construction rules out the possibility of
an ( log TiPT log log
-competitive algorithm.
Proof. By Yao's principle, the expected cost of 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 flec. we shall construct a family of randomized instance, so that the expected cost of any deterministic algorithm is at least 0 log 3E
>competitive.
log log 12
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 of the tree, the distance between i and its children is 1 times m the distance between i and its parent. That is to say, the distance between a height vertex and its children of height: + 1 m Let the height of the tree be h.
The demand sequence is consisted of h + phases. For each 0 S i S h, the (i 1)-th phase, m demand points arrive consecutively at some vertex of height i. For i > 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
h
h-1
h-1
D
m
= + hD m
m
m 1
m
m
m m-1
-
j=1
1=0
This value serves as an upper bound of the optimal cost. Le., OPT < 1 + hD m T-
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 7o 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 1/
We prove lower bound on the expected cost of any deterministic algorithm. We first overlook the first few phases until the subtree of the current demand vertex has diameter less than 77 Let it be the h phase. We now focus on the cost induced after the h' phase and notice that the predictions are useless as they are just the demand points. When the m² demand points at vertex of height& i comes, we consider the following two cases:
Case There is no facility opened in the current subtree. Then we either open a new facility bearing opening cost or assign the current demands to facilities outside the subtree bearing large connection cost at least m per demand. So the cost of this vertex is min Dm).
Case 2:
There has been at least one facility opened in the current subtree. Since the next vertex uniformly randomly chosen in its two children, the expected number of facility that will not enter the next phase subtree is at least We call it abandoned. The expected sum of abandoned facility is of the occurrence of case 2. Thus the expected cost in every occurrence of case 2 is 3
We carefully choose D, m. h so that 1) mDD = 1; 2) the total number of demand points is n, i.e.
Σ m' = n; and 3) D = T)x. These conditions give that (h + 1) log m = loog n, (h' + 1) log m mn
log 7 Consequently, h h- hh'
log mi/ Ing m
To sum up, an lower bound of any deterministic algorithm is (h - h²) min mD) = S2
log mis log
while the optimal cost is at most 1 + hD m m-I
O
log x m log
Setting m
log n log log n
the optimal
17

---

cost is O1)). And we prove the claimed lower bound of C2 log Finally, it is straightforward to see that the summation of the prediction error 7 s OPT OI)).
log log
G 1-OUTLIER SETTING
Observe that our main error parameter T could be very sensitive a single outlier prediction that has a large error. To make the eπror parameter bahave more smoothly, we introduce an integer parameter S S n, and define 7/20 the I-th largest prediction error, i.e., the maximum prediction error excluding the high-error outliers. Define 7) similarly.
In the following, stated in Theorem G.I, argue that our algorithm, without any modification (but an with an improved analysis), actually has a ratio of O(log(1 + () + log OPT that holds for every
un This also means the ratio would be minigesn O(log(1 t) log OPT), ), and this is clearly generalization of Theorem 1.1, since 1/50 T/po when / 1.
Moreover, we note that our lower bound, Theorem 1.2, still valid for ruling out the possibility of replacing 7h with 7/i in the abovementioned ratio, since one can still apply Theorem 1.2 with t 1. However, it is an interesting open question explore whether or an algorithm with (1)
ratio like Oglog + OPT) for some specific 1. (e.g., 2 vn) exists.
Theorem G.1. For every integer S S n, Algorithm is O(log(t + +
un!2)
((p))))-oee -cmmpptteiiivee. min n, (1, log OPT
Proof sketch. Let F (11, ....... I--1) be indices of the - 1 largest prediction error d(spred soop). The high level idea to break the dataset into a good Xa (z, [n]\D} and a bad part XB == (a; : E T according to whether or not the prediction within the outlier, and we argue that the expected cost of ALG on Xa is O mg show the expected cost Xa is Olog(t + 1)) times.
((PT) times larger than that in OPT, and
For the good part XG. we let X- (f*) = X( and apply a similar analysis as in the proof of Lemma 3.5 to show that
1) 5O max 1, log OPT
(e) Terjec
(m(r))
Σ (F*
(x))
10 (((+)
d(s,5*) xEX-
Σ
For the bad part XB. assume all predictions for points in XB of infinite error (which could only increase the cost of the algorithm), and let (f*) == Xf")) nT. Then this lies the case of Section E, where 71/ 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 E and the analysis for the short distance stage, have
(w(F))
E
(x)
Ollog( + 1))
w((')+
Σ d(z, 8r) xEX-(1-)
-E-+(1-)
We finish the proof by combining the bound for the two parts.
18


Reviews:
[{"review_id": "wtTwD61BAih", "reviewer": "Reviewer_TTSB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths of the paper:\nThe paper is reasonably well written for most parts -- except perhaps please provide a bit more description of the algorithm instead asking users parse through the pseudocode. The non-uniform case requires a non-trivial amount of analysis and may be of interest to the community.\n\nWeaknesses of the paper:\n\nWhile theoretically the problem is interesting -- I am not convinced of the practicality of the model. How will you construct a model that can predict what facilities an optimal solution would pick -- it depends on the other facilities that have already been chosen -- so what dataset would you use to train such a model?   In the \"real datasets\" based experiments, this important aspect is simulated using a 3-approximation algorithm to find the optimal solution and then randomized in accordance with \"prediction error\" n_\\infty.  This needs to be clarified. \nWhile the non-uniform case is interesting -- as opposed to the uniform case, which is down right trivial, and needs a good bit of work to prove, the idea is quite straightforward and predictable. Indeed, the doubling trick (used because, we do not need n_\\infty) is quite common place in the field of approximation algorithm -- ski-rental problem (Purohit et al) for example uses a similar trick. \nLastly, as a pedantic issue, I would really question the suitability of this work in ICLR. There is no ML/AI, if one discounts the vague motivation (which I have issues with as well). \n", "summary_of_the_paper": "The paper studies the classic problem of Online Facility Location augmented with a prediction model. The main contribution is a logarithmic competitive ratio algorithm for the case where facility opening costs are non-uniform.", "summary_of_the_review": "The key issue that needs to be addressed is the motivation for assuming that new facility locations can be predicted using a machine learning model. I feel this is quite unrealistic and significantly diminishes the value of the paper. It would be great if the authors could address this issue in the rebuttal phase. Otherwise, I think theoretically the paper is worth publishing, albeit at a more theoretical computer science (such as ESA, or APPROX ). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "scYrJu6Z-_k", "reviewer": "Reviewer_m2EN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper is giving a near-optimal result for online facility location with predictions, along with a nearly-matching lower bound. The only other result is the Fotakis et al. paper the authors discuss in the intro, which only considers the setting where all facilities have opening cost 1, whereas this paper handles non-uniform opening costs; even ignoring the correctness issues of the Fotakis et al. paper brought up by the authors, the algorithm's prediction step is to the best of my knowledge a novel one, i.e. it is not simply lifting a technique from another paper, and the difference between the weighted and unweighted setting is a key technical challenge in their results. So I would view this as a substantial improvement over the Fotakis et al. paper, even if the Fotakis et al. paper is correct/gets a better competitive ratio in the setting where $\\eta_1$ is small (although I agree with the authors that the bound claimed in the Fotakis et al. paper is somewhat fishy due to the fact that it could be negative when $\\eta_1$ is large compared to $\\eta_\\infty$, and was not able to discern from reading that paper where the catch is). Furthermore, the design of the prediction step is fairly non-trivial to me, but after reading the paper I felt I had some good intuition for why this was the right way to use the predicted facilities, i.e. that the prediction step had a nice intuitive explanation. The experiments also nicely supplement the theoretical results. While the lower bound construction is not particularly novel by itself (I believe it is a modification of a lower bound proof for OFL without predictions), the bound itself nicely complements the upper bound as well. \n\nMy main criticism of the paper is the presentation of the lower bound, in particular the claim that the lower bound shows that a bound on $\\eta_1$ instead of $\\eta_\\infty$ is unlikely to offer substantial improvements. The authors state that their lower bound holds even when $\\eta_1 = O(1)$. However, in the lower bound example, the distances in the metric could be smaller than one, i.e. the ratio $\\eta_1/\\eta_\\infty$, which is e.g. not changed by just rescaling the metric, and is in my view the right quantity to look at, might still be quite large. So this doesn't say anything about the relation between $\\eta_1$ and $\\eta_\\infty$, i.e. this ratio can vary depending on the setting of $\\eta_\\infty$ in their example (roughly, $\\eta_1$ is fixed but $\\eta_\\infty$ can be varied). I think if $\\eta_\\infty$ is sufficiently small in their lower bound one gets $\\eta_1 = O(\\eta_\\infty)$, which shows that in general no $o(\\frac{\\log n\\eta_1/OPT}{\\log \\log n})$-competitive algorithm is possible, which would e.g. say that one can't get a better asymptotic ratio by replacing $\\eta_\\infty$ with $\\eta_1$, but I'm not completely sure if this is the right takeaway, and the authors don't spell out any argument like this. I would like to see the relationship between $\\eta_1$ and $\\eta_\\infty$ stated more clearly in this lower bound, as well as a discussion of what this relationship implies about bounds depending on $\\eta_1$, if the authors wish to make claims that $\\eta_1 \\ll \\eta_\\infty$ is unlikely to help like they do in the introduction.\n\nAlso, I don't believe it is mentioned anywhere that OPT does not have to be the offline optimal solution in the analysis, which is implicitly being used in the lower bound - in this lower bound, $\\eta_\\infty$ is the distance between the predictions and a solution which may be optimal. For clarity's sake it would be good to either mention this somewhere, or the lower bound construction should prove the one-facility solution is optimal; if anything the former should strengthen the upper bound result by making it more general, and it would be more in line with the empirical results, which don't find an exact solution to base predictions off \n\nLastly, less so a weakness than a lack of strength, while online facility location is a fairly fundamental question in the online algorithms space, I don't think that compared to e.g. \"The Primal-Dual method for Learning Augmented Algorithms\" by Bamas et al., this paper's techniques are fundamentally breaking new technical ground in the learning-augmented space that could offer insights into other problems. Again, I wouldn't view this a weakness, just a reason why I don't feel I can rate this paper highly despite enjoying reading it.", "summary_of_the_paper": "The paper considers the online facility location problem with predictions. In this problem, there is a set of facilities given offline on a metric and a sequence of demand points appearing online. When a demand point arrives, we must either route it to a facility we have previously opened, or open new facilities and route the demand to one of the new facilities. The total cost of a solution is the total cost of facilities opened, plus the total distance between each demand point and the facility it was routed to. In the learning-augmented setting, when each demand point arrives we are also given a prediction, in the form of a facility we believe it is routed to in an optimal solution. Let $\\eta_\\infty$ be the maximum distance between any the facility we predict a demand point is routed to in the optimal solution, and the facility it is actually routed to in the optimal solution. The authors give a $O(\\log \\frac{n \\eta_\\infty}{OPT})$-competitive algorithm, where $n$ is the number of demand points and $OPT$ is the cost of the optimal solution - without loss of generality, we can assume $\\eta_\\infty = O(OPT)$, so this is at worst an $O(\\log n)$-competitive algorithm. They also show that this is the optimal competitive ratio up to $O(\\log \\log n)$ factors, even if $\\eta_1$ (the total distance between predictions and OPT's facilities rather than the maximum) is constant. The authors also give experiments showing that on real-world data sets with synthetic predictions that have a bounded $\\eta_\\infty$ value, their algorithm outperforms Meyerson's when the prediction error is low, outperforms following the predictions when the prediction error is high, and is not too much worse than Meyerson's when the prediction error is high.\n\nThe algorithm the authors use first uses the algorithm of Meyerson for the setting without predictions. In this algorithm, for each power of 2 $2^k$, we consider opening the closest facility to the demand point whose cost is at most $2^k$, or that is already in our set of open facilities. Let $\\delta_k$ be the distance from the demand point to this facility. We open this facility with, roughly speaking, probability proportional to $\\frac{\\delta_{k-1} - \\delta_k}{2^k}$. Intuitively, we will never open a facility that is further from the demand point from a previously opened facility, and the probability we open a facility closer than the best previously opened facility is roughly proportional to the decrease in connection cost from opening this facility versus the best facility costing half as much, divided by this facility's opening cost. Following a round of Meyerson's algorithm, we use a \"prediction step\" to possibly open more facilities, whose expected cost is at most the increase in facility and connection cost in the round of Meyerson's algorithm. To do so, we consider facilities in a ball around the predicted facility whose radius is proportional to the distance from the predicted facility to the nearest facility opened in a previous prediction step, and consider opening the cheapest one. We will definitely open it if doing so would not cause the cost of the prediction step to exceed the cost of the round of Meyerson's algorithm, otherwise we open it with some probability, such that the prediction step's expected cost is exactly the cost of the round of Meyerson's algorithm. ", "summary_of_the_review": "Overall I think the paper is a weak accept, if the aforementioned concerns with the presentation of the lower bound construction can be resolved (if they are not resolved in the rebuttal period, I would rate at a weak reject). I think the algorithm and its analysis are fairly non-trivial but intuitive and enjoyable to read about, the problem being addressed is one of interest, and the lower bound/empirical results nicely complement the upper bounds. However, it is not clear to me if this paper stands out in particular amongst other papers in the learning-augmented online algorithms literature, and there are some concerns with the presentation of the lower bound I wish to see addressed before publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WWjJdI0cAqk", "reviewer": "Reviewer_tWdT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is very well-written and does a good job of explaining the key ideas behind the algorithm and proof techniques. The algorithm itself is quite natural and also likely to be useful to practitioners - essentially, the proposed algorithm is to use Myerson's algorithm for online facility location and then open an additional facility at the predicted location whenever Myerson decides to open one. The key technical contributions are for the variant when facilities have non-uniform costs, in which case the additional facilities are opened \"near\" the predicted location. \n\nThe proposed algorithm obtains a competitive ratio of $O(log (n \\eta_\\infty/OPT))$ where $\\eta_\\infty$ is the maximum prediction error. So the algorithm only improves upon the worst-case setting as long as each prediction is $<< OPT$. The authors also demonstrate a matching lower bound though, and in particular show that the dependence on $n \\eta_\\infty$ is unavoidable.\n\nQ. Is it easy to compute the \"consistency\" of the algorithm, i.e., the competitive ratio when the predictions are perfectly accurate? Can one try to obtain a $(1+\\epsilon)$-consistent (but also robust) algorithm?\nQ. Can the robustness bound be improved to $O(\\log n / \\log \\log n)$?\n\nMinor comments:\n- Abstract: The last sentence of the first paragraph needs some punctuation\n- Page 4: Last line of Section2. \"0\\leq k \\leq L\" --> \"1 \\leq k \\leq L\" ?\n- Page 5. Last line. \"in by Lemma 3.5\" --> \"is by ...\"\n- The statement of Lemma 3.6 bounds $cost_M()$, but the proof only bounds $cost_P()$. It will be good to remind readers that the expected cost is the same.\n \n\n\n", "summary_of_the_paper": "The paper studies a variant of the online facility location problem where each demand point arrives with a prediction of which facility it is assigned to in an optimal solution. In line with recent work on learning-augmented algorithms, the paper designs an algorithm whose performance degrades gracefully with the quality of the predictions and yet retains an almost optimal worst-case guarantee.", "summary_of_the_review": "Overall the paper is a nice addition to the new area of learning-augmented algorithms. The proposed algorithm is practical and almost optimal, though it would be nice to obtain the optimal robustness bound of $O(\\log n / \\log \\log n)$. The paper seems to be a good fit for ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RnMuIZ6DUBk", "reviewer": "Reviewer_DWJH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper follows a recent line of work in considering online algorithms with error-prone predictions.  The main results are an online algorithm for online facility location in this setting and a nearly matching lower bound, which are interesting.  The experimental evaluation is reasonable, but not overly exciting since the improvement over Meyerson's algorithm seem to be very narrow in some cases.  The presentation is mostly clear, but some improvements could be made, especially to the analysis.  Overall, I would be okay with accepting this paper.  See below for some further comments/suggestions.\n\nThis paper considers the predictions as coming from an oracle.  Recent work has started to explore the question of how to construct predictions for online algorithms from past data, e.g. [1,2,3] below.  It would be interesting to explore how to construct predictions for online facility location from past data, especially for an empirical evaluation.\n\n[1] - Customizing ML Predictions for Online Algorithms.  Anand et al. ICML 2020\n\n[2] - Learning Online Algorithms with Distributional Advice.  Diakonikolas et al. ICML 2021\n\n[3] - Learnable and Instance Robust Predictions for Online Matching, Flows, and Load Balancing.  Lavastida et al. ESA 2021\n\nSome suggestions for the related work section, which could be fleshed out more:\n - Purohit et al. 2018 also considers non-clairvoyant scheduling on a single machine\n - Secretaries with Advice.  Dütting, et al. EC 2021. also considers the secretary problem with predictions.\n - Flow Time Scheduling with Uncertain Processing Time. Azar et al. STOC 2021 and Online Scheduling via Learned Weights. Lattanzi et al. SODA 2020 consider flow time scheduling and online load balancing, respectively, in settings with error-prone predictions.\n\nMinor comments/suggestions\n - At the end of page 1, \"such as experts' advices\" -> \"such as expert advice\"\n - In the \"Calibrating predictions\" paragraph, \"second last\" -> \"second to last\"\n - In the \"Calibrating predictions\" paragraph, $\\frac{n \\eta_\\infty}{OPT} = O(\\log n)$ should probably be $\\frac{n \\eta_\\infty}{OPT} = O(n)$\n - In the proof of lemma 3.6, \"the fact that we does not\" -> \"the fact that we do not\"\n - Paragraph before lemma 3.8, \"let $\\bar{\\ell}$ be the integer that\" -> \"let $\\bar{\\ell}$ be the integer such that\"\n - In the experiments, the four plots seem to have different scales on the x-axis.  This seems to be due to the differing distance scales across each dataset.  It might be helpful for the presentation to either explain this in the text or maybe present the plots with something like $n\\eta_\\infty / OPT$ on the x-axis.\n\n------------------------------\n\nEdit after reading author responses:\n\nThe author's responses have cleared up my questions.  I appreciate the experiments with the simple predictor, which seems reasonable to implement in practice and performs well on the considered datasets.  I have raised my score to accept.\n", "summary_of_the_paper": "This paper considers the online facility location problem with predictions.  In this problem, there is a sequence of points which arrive online and the algorithm must either open a facility to serve each point, paying the facility opening cost plus the distance to the opened facility, or it can assign the point to an already open facility, paying the distance only.  Additionally, each arriving point is given a prediction of a facility which serves it in an optimal solution. The goal is to be competitive with the offline optimal solution, and the competitiveness is parameterized by the error in the predictions.  Here, the prediction error is the maximum distance between a predicted facility and the facility in the optimal solution which serves a point.\n\nThe main result is an algorithm which is $O(\\min (\\log n, \\log \\frac{n\\eta_{\\infty}}{OPT}))$-competitive, where $\\eta_\\infty$ is the max error and $OPT$ is the optimal cost.  This improves over worst case lower bounds when $\\log \\frac{n\\eta_{\\infty}}{OPT} = o(\\frac{\\log n}{\\log\\log n})$, and nearly matches worst case bounds otherwise.  At a high level the algorithm first follows Meyerson's algorithm, then opens some additional facilities by taking into account the predictions.  In order to get the stated bound, the predictions are \"calibrated\" so that $\\eta_\\infty = O(OPT)$ so that $\\log \\frac{n\\eta_{\\infty}}{OPT} = O(\\log n)$, thus it suffices to only prove the bound of $O(\\log \\frac{n\\eta_{\\infty}}{OPT})$.  A lower bound is also given, showing that the result is nearly tight.\n\nAdditionally, an experimental validation is carried out, comparing the proposed algorithm with Meyerson's algorithm and a naive algorithm which follows the predictions.  The experiments are performed on datasets where the underlying metric is either Euclidean or a graph metric.  The predictions are simulated to have a given level of error.  While the proposed method underperforms against blindly following the predictions when the error is small, it is more robust to large prediction errors and often comes close to Meyerson's algorithm when the prediction error is large.", "summary_of_the_review": "This paper considers a fundamental online problem in the presence of predictions with a nearly tight result for this setting.  The experimental validation is reasonable.  Some improvements could be made to the presentation, but it is currently clear.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RBefOraCJjD", "reviewer": "Reviewer_m1RY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength of this paper: The paper gives a natural relation between prediction error and competitive ratio for a classical online problem. Furthermore, the lower bound presented in the paper makes the competitive ratio of their algorithm near-optimal. Due to this, I find overall result in this paper to be a nice one. \n\nOn the technical side, the authors present a fine-grained analysis of Meyerson’s algorithm parameterizing the competitive ratio on the prediction error. Although it appears somewhat straight-forward, it seems to be a nice contribution.\n\nWeakness:\n\nI have three sets of concerns/criticisms.\n\na)\tTheir algorithm uses the worst-case algorithm by Meyerson as a black box to guide its decisions. A more natural approach would have been to incorporate predictions within Meyerson’s algorithm. Their experiments seem to suggest that even with perfect predictions, the empirical gains over Meyerson’s algorithm seem only minor. I suspect that relying on Meyerson’s cost as a black box may be the main reason for this. Indeed, the authors explicitly state that they do not make any attempt to reduce the hidden constant within the big-O notation of the competitive ratio. So, there may be other algorithms that have a similar theoretical trade-off but do significantly better in practice.\n\nb)\tThere are several presentation issues in the paper. These include undefined notations, typos, and (minor) inaccurate lemma/theorem statements. I point some of them out below. These issues make it challenging to fully verify and appreciate the theoretical claims, especially in a short time frame. Experimental result section is somewhat confusing as well. The authors do not explain their choice of data sets and what makes these data sets “real” for the facility location problem. Also, how are the non-uniform costs assigned to facilities for the non-uniform data set?\n \nc)\tFinally, I do not see why this prediction model is natural for this problem. How can we use historical data to generate predictions with small \\eta value?\n\n\nPresentation issues are listed below:\n\n1)\tOPT is defined to be a value sometimes and a set of facilities on some other occasions (For instance in the statement of theorem 1.1)\n2)\tCan $\\eta_\\infty$ be 0? If so, how should we interpret your competitive ratio?\n3)\tSection 1.2 paragraph 2, there is a missing \\log is the competitive ratio of Meyerson’s algorithm\n4)\tSection 1.3 determined -> deterministic\n5)\t$f_{open}$ is not initialized in the procedure PRED. L23 of the algorithm uses it without any initialization\n6)\tA short overview of Meyerson’s algorithm in the Preliminaries can be very helpful.\n7)\tLemma 3.5 $X(f^*)$ is undefined.\n8)\tTheorem 1.2 Should it be for $\\eta_{\\infty} > 0$?\n9)\tPage 6: “we does” does not seem correct.\n10)\tPage 6, line 1 “that” -> “such that”. This seems to be a recurring issue.  \n11)\tThere are several other typos. A careful proofreading of the paper is necessary for it to be of publishable quality. \n", "summary_of_the_paper": "This paper studies the classical online facility location problem in a metric space. Given a new demand in this space, the algorithm will either open a new facility by paying an opening cost $w(f)$ and assign the demand node to this facility, or it will assign the demand node to an existing open facility. The cost incurred by the algorithm is the sum of all the opening costs and assignment costs.\n\nIn this paper, the authors consider the setting where, along with every demand node, we are also given a prediction on which facility it gets assigned to in the optimal. Such predictions can potentially be acquired through historical data. \n\nTheir main contribution is an online algorithm for facility location with predictions that has a near-optimal competitive ratio. The competitive ratio relies on a parameter $\\eta_\\infty$ which is simply the largest prediction error, where prediction error for any demand point is the distance between the predicted facility and the facility that is assigned to the demand in the optimal solution.\nIntuitively, the authors show that if the predictions are accurate (i.e., $\\eta_\\infty$ is small), then their algorithm is $O(1)$-competitive. On the other hand, if the predictions are highly inaccurate, the algorithm will become $O(\\log n)$ competitive. \n\nThe algorithm relies on an $O(\\log n)$ competitive worst-case optimal (randomized) online algorithm by Meyerson. The idea becomes very simple when facilities have uniform opening costs: Suppose Meyerson’s algorithm opens a facility, one can simply also open a facility at the predicted location. By doing so, the cost incurred will not be more than twice that of Meyerson’s algorithm which is $O(\\log n)$-competitive. However, when the predictions are accurate, opening the facilities at predicted locations lead to better future assignments leading to $O(1)$-competitive algorithm.\n\nThey extend this approach in a non-trivial way to the case with non-uniform opening costs.\n", "summary_of_the_review": "Due to the weaknesses mentioned above, I do not believe the paper is ready for publication.\n\nUpdate: Thank you for addressing my concerns. After reading the new version, I am happy to update my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "F2EZz9N0jK", "reviewer": "Reviewer_3sjS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The paper is technically solid, and the analysis, although it builds heavily on Meyerson's analysis, is non-trivial. I would say that from a purely technical perspective, the paper passes the bar for the conference.\n2. The facility location problem is an important one. While I am generally inclined more toward papers that develop general purpose tools for the online algorithms with predictions area instead of giving very specific algorithms for particular problems, I think online facility location is a problem that is fundamental enough that it merits study in this framework. (As the paper mentions, this is not the only recent paper on this very problem, although the results are in this paper are more general in that they apply to on-uniform opening costs.)\n\nWeaknesses:\n\n1. I am really not convinced by the error model in this paper. It bases the error on the worst prediction, which means a large error even with one bad prediction (and every other prediction is precisely correct). The paper tries to justify this by showing that the worst case error cannot be replaced by the sum of prediction errors. But, to me, the right solution to this would be to have two components of the error: one component that counts the number of mispredictions (where the distance by which the prediction missed is irrelevant), and the other that captures the $\\ell_1$ distance for the correct predictions (that might still not be exact). (Of course, what is counted as a misprediction and what is counted as a correct prediction is not canonical, but the algorithmic guarantee can hold for any such choice.) This would naturally interpolate between robustness (where all predictions are counted as mispredictions) and consistency (where all predictions are correct predictions and the error distance is 0). Instead, this paper replaces $\\ell_1$ error with a very loose upper bound of $n$ times the $\\ell_\\infty$ error, which as I mentioned above, wouldn't give anything better than an online algorithm (without predictions) even if one prediction is badly off.\n\n2. My second concern (and question to the authors) is the dependence of this algorithm on Meyerson's algorithm. The way the algorithm is set up, it takes the solution produced by Meyerson's algorithm and uses the budget provided by this algorithm to essentially reduce future costs by buying facilities \"near\" the predicted facility. What if we replaced Meyerson's algorithm with another competitive  facility location algorithm? If the algorithm can use any competitive facility location algorithm, that has multiple benefits: (a) the algorithmic framework being designed is more flexible, and can be applied to other similar problems instead of designing another algorithm from scratch, and (b) much of the analysis, which at the moment reprove properties of Meyerson's algorithm, can be eliminated and simplified. As stated, the current algorithm seems to rely on specific properties of Meyerson's algorithm, but is that really necessary?\n\n3. One minor gripe is the way the algorithm is presented in this paper. Could you please include a text description (perhaps in addition to the pseudocode) so that one doesn't have to understand the algorithm solely from the pseudocode?", "summary_of_the_paper": "This paper presents an algorithm for online facility location with predictions. The prediction model is that on the arrival of each client, the prediction provides a facility to connect this client to. The quality of the prediction is quantified in the result by the maximum prediction error, i.e., the maximum distance between the locations of the predicted facility and a facility serving the same client in a fixed optimal solution. The main result is that the competitive ratio is constant (which is the best offline ratio) when the maximum prediction error is small (e.g., when it is a 1/n-fraction of the optimal cost, which of course if true when the predictions are precisely correct), and O(log n) (which is the best online ratio, ignoring lower order terms), when the prediction error is large. The algorithm is an augmentation of an online algorithm for the problem by Meyerson that obtains a competitive ratio of O(log n), where in each step in addition to running Meyerson's algorithm, the algorithm uses a second copy of the incremental cost in Meyerson's step to preemptively open more facilities \"close\" to the predicted facility for the current client. In addition to the theoretical analysis, the paper includes an experimental evaluation of the algorithm comparing it to baselines produced by an algorithm that blindly trusts the prediction and Meyerson's algorithm.", "summary_of_the_review": "This is a credible paper on online facility location with predictions. The problem considered is important and relevant, and the results obtained are tight in the sense that consistency and robustness results in the right ballpark. But, I have concerns about the error metric, which is the most important parameter here - with the current error metric, the very realistic possibility of having a single bad prediction is also going to relegate the guarantees of the algorithm to those of having no prediction at all. I would also have been happier with an algorithm that can use an online algorithm for the problem in a more black box manner - this would make the framework more generally applicable (and I suspect this is possible even with the current framework, or some modification of it, because I don't see the framework as conceptually using anything specific about Meyerson's algorithm, although I might be wrong on that last point).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the recent line of work on algorithms with predictions.  They give new results on the online facility location problem. Overall, the reviewers felt the topic was of interest to the community.  There were some concerns about the error metric used and the overall framework. However, the majority of reviewers still felt the paper was interesting and I think the paper can be accepted.
Decision: Accept (Poster)