Online Facility Location with Multiple Advice
Authors: Matteo Almanza
Flavio Chierichetti
Silvio Lattanzi
Alessandro Panconesi
Giuseppe Re
Venue: NeurIPS 2021 Poster (2021)
Keywords: Clustering
Facility Location
Online Algorithms
Machine-Learned Advice
Online Clustering

Abstract: Clustering is a central topic in unsupervised learning and its online formulation has received a lot of attention in recent years. In this paper, we study the classic facility location problem in the presence of multiple machine-learned advice. We design an algorithm with provable performance guarantees such that, if the advice is good, it outperforms the best-known online algorithms for the problem, and if it is bad it still matches their performance.
We complement our theoretical analysis with an in-depth study of the performance of our algorithm, showing its effectiveness on synthetic and real-world data sets.

Online Facility Location with Multiple Advice
Matteo Almanza
Flavio Chierichetti
Silvio Lattanzi Google Research Zurich, Switzerland sil salviol@google. com
Dipartimento di Informatica Sapienza University
Dipartimento di Informatica
Sapienza University Rome, Italy
Rome, Italy
almanza@di www.:/aadd..iiimmm.....mm uniroma1.1t
flavio@di uniromal. it
Alessandro Panconesi
Giuseppe Re
Dipartimento Informatica
Dipartimento Informatica
Sapienza University
Sapienza University Rome, Italy re@di www.umni.......
Rome, Italy
ale@di umiroma1..t
Abstract
Clustering is central topic in unsupervised learning and its online formulation has received a lot of attention in recent years. In this paper, we study the classic facility location problem in the presence of multiple machine-learned advice. We design an algorithm with provable performance guarantees such that, if the advice is good, it outperforms the best-known online algorithms for the problem, and if it is bad it still matches their performance. We complement our theoretical analysis with an in-depth study of the performance of our algorithm, showing its effectiveness on synthetic and real-world data sets.
Introduction
Clustering is central topic in unsupervised learning [Jain and Dubes 1988 Aggarwal and Reddy
Gan et al. (2020) In the past few years, its online version has gained lot of attention [Zhang al. 2004 Liberty al. 2016 Lattanzi and Vassilvitskii 2017 Cohen-Addad al. 2021 In this paper we are interested in the fundamental question of whether machine-leared advice, especially when coming from multiple sources, can boost the performance of clustering algorithms in the online setting. In particular, we are interested in designing online algorithms with access to multiple advice that exhibit strong theoretical guarantees together with a good experimental performance.
2014
To explore the interplay between online algorithms and multiple advice we focus on facility location, classic clustering problem with long and rich history computer science and operations research Korte and Vygen 2018), which can also be seen as the Lagrangian relaxation of m-meian clustering, In the online setting of k-median clustering, it is easy to see that the requirement of having clusters is hard constraint then the cost of solutions is bound to be arbitrarily far from the optimum, which makes the straightforward online formulation rather uninteresting algorithnically. There two standard ways in which the constraint can be relaxed: bi-criteria solutions and the Lagrangian relaxation. Facility location captures the latter.
In the online version of facility location, points arrive in sequence and, as soon as a point arrives, an irrevocable decision must be made: either assign it existing opened facility we open new one to serve it. Each facility, therefore, induces cluster, consisting of the points assigned to it. The cost of this sequence of decisions is given by the of the service costs (i.e. the distance between point and its facility) and the total facility cost (opening each facility has cost, which in this paper we assume be uniform). The goal is to find cheap clustering as possible. This online version
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

was first introduced by Meyerson [001] who gave an elegant (l)) approxxmattn algorithm.
and studied extensively thereafter Fotakis 2003 2005 2011 Cygan et al. 2018 [ohen- Addad et al., 2019 Ahmed et al. 2020. Guo et al. [020]] One of the main reasons for this heightened attention is that even in dynamic settings the resulting clustering is very stable. This is particularly useful in real-world systems where clusters are served directly to users or when they are used in downstream machine learning model, a situation where modifying the clustering would incur too high a cost.
In real-world applications, one typically has side information that could help solve the online clustering problem. This natural scenario is a recurrent theme in machine learning that focuses on how to take advantage of expert advice. In the context of online algorithms, Lykouris and Vassilvitskil (2018) and Mahdian et al. [2022] introduced formal framework for online problems within which mathematically rigorous performance guarantees can be given in terms of the quality of the advice. In particular, they showed how to incorporate the advice in a robust way: the advice is exploited when is good and disregarded when it is bad. All this happens automatically: the robust algorithm does not need know in advance which is which. Remarkably, when the advice is bad the performance of the best online algorithm is matched. The approach combines mathematical rigor with practical effectiveness, adding the desirable dimension of robustness. The solution we develop for facility location is in the same spirit, with focus on multiple advice which adds an important new dimension. Thus, the goal of this paper is to show how to take advantage of multiple advice within this rigorous algorithmic framework in the case of online facility location.
In our set-up the advice comes in the form of a family of sets, each suggesting a list of facilities to open. As we show with our experiments, multiple advice of this form can be easily and efficiently produced on the basis of past data. The main technical result of this paper is the following. Suppose we have family of sets S,,..., St. which intuitively represent sets of suggested facilities to open, and let S be their union. We develop an online randomized algorithm, called TAKEHEED, that computes solution whose expected cost is
O (log((S)) . OPT(S)),
where OST is the best solution that can be obtained using only facilities in S. Notice that the OPT(S) factor is no worse than any of the suggested sets in isolation since OPT(S) S min, (S.(S.). In fact, it can be much better. For instance, every set could contain just few good points and a lot of noise. Or, one of the sets could be good but its identity unknown. And yet, TAKEHEED separates the wheat from the chaff and delivers near-optimal solution. This result (which is the main technical step toward the solution) can be seen as a solution to the version of facility location in which the facilities are constrained to be in a specific set, as opposed to the entire input metric space. The above result is essentially the best possible. In Section 4. we prove that the log |S] factor is near-optimal.
We also show that the best-known algorithms (see Meyerson (001], Fotakis 2003 2005) ) cannot match the same bound, for they can only attain an ((( approximation factor in general. This is a strong indication that techniques different from those employed by those state-of-the-arr algorithms are required for this problem, providing compelling motivation for our approach which is based on the theory of Hierarchically Separated Trees (HST's) introduced by |Bartal (1996] in a seminal paper.
On the practical side, our experimental analysis with real and synthetic data shows that it is easy and inexpensive to compute multiple advice of the form described, allowing TAKEHEED to outperform state-of-the-art algorithms such as those in Meyerson] (200T), |Fotakis (2003), AAngnostopoolos et al. 2004). Furthermore, we also show that we can make algorithm robust to erroneous advice: when S is far from any optimal set of facilities for our input, OPT(S) can be much larger than the actual offline optimum OPT. However, by combining TAKEHEED with known results of Mahdian al. (0122) we can get a robust version of TAKEHEED called WARY, whose cost is
o (min log((S)) OPT(S),
log(n) OPT )) log (n)(n)
Note that the second term matches the best possible bound, in view of the lower bound Fotakis [003)] Our experiments confirm the good behavior in practice of this robust version. Indeed,
outperforms other state-of-the-ar robust solutions.
One of the appealing features of TAKEHEED is that it leverages multiple advice simple way. The algorithm however could suffer from an "adversarial" attack of sorts. If very large bad sets of suggested facilities are given as part of the advice, the theoretical guarantee, which depends on the cardinality of the union of the advice sets becomes uninteresting. To deal with this we design

---

BUCKETHEED, an algorithm that is resilient to the presence of such large, bad advice. If the best advice set is Si,, the expected cost of the solution produced by this algorithm is
O (log log(n)) (log(k) log((S,- ()) OPT(S,)).
This result is mainly of theoretical interest. Indeed, one of the strengths of TAKEHEED is that in practice small advice sets are easy to obtain and the term log( SS)) is going to be quite small, making the overall approach very actionable.
Related Work. Facility location and online algorithms have been extensively studied in the algo- rithm and machine learning literature. Here we give a high-level overview of the main results.
Facility Location. The offline metric (uncapacitated) facility location problem has been extensively studied, and various algorithms and heuristics have been formulated (see Korte and Vygen (2018)) The problem is known to be NP-hard, and it cannot be approximated within a factor of 1.463 unless
NP C (TTIE( log log(n)) Guua and Khuller 1999]. The best-known polynomial- algorithm
yields 1.488 approximation ratio [Li 2013].
Online Setting. We cast our results in the standard setting of online competitive analysis [Borodin and EI-EE-aaa Yaniv [005]. The online version of the metric facility location problem was introduced by Meyerson 200T]. together with a randomized algorithm providing an expected (log(n)) approxi- mation of the optimal solution. Subsequently, [otakis [ottee
[2003] provided a deterministic algorithm with a (log(n)) (n)/ log ln)( competitive ratio and proved that no randomized algorithm can obtain an asymptotically better competitive ratio against an oblivious adversary. even if the points lic on a line. Anagnostopoulos et al.] [2004) also provided an online algorithm for facility location with restricted facilities: their algorithm works only in the euclidean plane, and our procedure combining the advice can be seen as a generalization of this result in generic metric space. Fotakis (2005) formulated a different algorithm for the general online problem, achieving O(log(n) (2)) approximation of the optimal cost with a primal-dual approach. Mahddaa et al. 2012] showed how to combine two online algorithms for facility location into a single algorithm achieving constant approximation of the costs of the best algorithm. In fact, the mixing procedure can be also be used to combine an algorithm with suggested set of facilities, or two sets of suggested facilities. Applied inductively, it can also be used to mix multiple advice. In asymptotic terms, the resulting bound is incomparable to ours (see the Supplementary Material) and, in practice, our approach appears to be preferable, as documented in the experimental section. Other formulations of online clustering have been proposed: Metuu and Plaxton| [003) allow to chose the order by which processing the input, which is provided in advance; Guo et al. [2020) consider the online model with recourse, in which one is allowed to close some facilities and reassign the clients to new ones. Guo et al. 20200 also use HSTs for their clustering problem, but in a different way to ours.
Online algorithms with learned advice. There have been various previous attempts to improve online algorithms with external information. Common assumptions are related to the distribution of the input data. The most popular assumption is that data arrive according to the random arrival model, i.. the input is a random permutation of a fixed unknown set of elements. This leads to major improvements in the competitive ratio for many problems [MeGregor 2014]. Even Meyerson's 's algorithm is shown to have a constant expected competitive ratio in this setting [Meyerson 2001 In many other scenarios, it is common assume that input data are sampled from fixed distribution, like for online matching (Mirrokni et al.] 2012] or job scheduling [Mitzenmacher, 2020). Recently, Lykouris and Vassilvitskii [2018) formulated the Online with Machine Learned Advice (OMLA) model, which is a theoretical framework for combining online algorithms with machine learning predictions. They also designed algorithm for the caching problem in this model, which has been improved by [Rohatgi] [2020) and Wei (2020). Various other problems have been tackled in this model with encouraging outcomes, like ski-rental Purrhii et al. 2018). the Secretaries problem (Dütting iet al. 22200). and scheduling with restricted assignments [Lattanzi et al. [2000] (see Mitzenmacher and Vassilvitskii (2020) for a survey). In a slightly different setting, Medina and Vassilvitskil 2017 designed an algorithm for reserve price optimization in auctions. Learned predictions have been also used improve classical data structures [Kraska et al.) 2018 Mitzenmacher] [018 (Hsu et al. 2019.. A different model is the advice model, in which there is an oracle knowing the exact input and providing a small part of it to the online algorithm (see Boyar et al. (2017) for a survey). Note that this oracle is supposed to be perfect and completely reliable, while in our setting, the predictions can be extremely inaccurate, nevertheless the online algorithm needs to be robust to them. Another different setting is the one of online learning with experts [Choromanska and Monteleoni 2012
3

---

here the advice, as the proposed clustering decisions, can change at every time step, while in our setting they cannot change over time.
Online Facility Location with learned advice. Very recent independent work in the same spirit as ours, made public ArXiv after the present paper was submitted, are Fotakis et al. [021] and Jiang ct al. 2022
2 Preliminaries
Let us begin by defining our problem: UNIFORM ONLINE FACILITY LOCATION. We are given a sequence of points P. called clients, possibly with repetitions, from a metric space X with distance d. and f > 0 called the uniform facility cost. The points are presented to us one after the other. As soon as point p arrives,
must select point c(p) E X, called an opened facility, and assign p to it. c(p) can be an already opened facility if exists, or a brand new point. At the end of this procedure, every client in p E P has corresponding facility c(p). Let h be the number of opened facilities at the end. The cost of the assignment is defined as h f + Epe pep d(p, c(p)). If we consider facility location as a Lagrangian relaxation of k m-ddiin,, then f plays the role of Lagrangian multiplayer (the larger the f. the fewer the clusters). To identify an instance of the problem is sufficient to specify the pair (P. without explicit mention of the underlying metric space (X, d), which is fixed and whose existence clear from the context. We adopt this convention from now on. We denote as OPTp, or simply OPT when the context is clear, the cheapest possible facility assignment for P. Sometimes the set of possible facilities will be restricted be finite set S. In this case, the optimum assignment will be denoted as OPT(P, S), or simply OPT(S).
We make extensive use of the elegant theory of Hierarchically Separated Trees (HST's). The theory was introduced in a seminal paper by Bartal 1996]. In what follows we mainly use the definitions and results of Fachharoenpoool et al. 2004). An HST family for finite metric space (X, d) consists of a family of rooted trees 7 and a probability distribution D over the trees of T satisfying the following properties. The leaves of every T E T the points of the metric space X. The edges of every tree in the family are weighted according to a simple scheme. First, the edges from a node to its children have the same weight. Second, if we follow any path from the root to leaf the edge weights decrease exponentially. In this paper we only consider 2 HSTs, so they always decrease by factor of at least 2. Each tree T' induces a simple metric dr among the leaves: the distance between two leaves u and v is the sum of the edge weights along the unique path between them in T. Fakcharocnphol et al. (2004) show that, given any finite metric space (X, d) is possible construct in polynomial-inn a 2 HST family (T, D) with this structure which moreover satisfies the following:
for every T' E T, and for all u, v E X, d(u, v) S (T(u,));
ii for all u, u E X, Brwoldr(u, (u, v)] & 8 llg(( d(u, v). All logarithms in this paper are to the base 2.
3 The Online Algorithm and Its Analysis
Recall our setting. We have an instance of the online facility location and multiple advice in the form of a family of sets, each suggesting set of facilities open. We would like to take advantage of these suggestions when they are good and ignore them when they are bad. The problem is that we do not know advance which is which. The main technical tool toward the solution is the following.
Theorem 3.1. Let (P, f) be an instance of uniform online facility location, let Si,..., Sg be sets of facilities (i.e. finite sets of points from the underlying metric space), and let S ;= U S,. Then, there is randomized online algorithm that assigns facilities of S to points in P whose expected cost is
O (log([S)) OPT(P,S))
Intuitively, the sets Si...., Sk play the role of multiple machine-learned advice. We shall refer to each S; as a suggested set. The first observation is that, (PT(P,S) S min;e COST(P,S) St), where COST(P, X) denotes the cost incurred by using all and only the facilities of the set X. Thus, we can approximate well the best suggested set. In fact, no suggested set by itself needs to be particularly

---

good. As long as their union contains a good subset, a good solution can be found! For instance, every suggested set could contain few good points and lot of noise. Yet, the algorithm would be able to extract a good solution. Notice that, even if the advice comes from many sources, we combine it in a very simple way: we take the union S of the suggested sets. We believe this is quite an appealing feature of our approach, However, the log((S)) factor shows that we could suffer from the presence of a few large and bad advice sets, Even this is not the case in practical settings, in the Supplementary Material we show how to deal with this problem [] the union contains no good subset, (ST(S) can be arbitrarily far from the true offline optimum OPT, so the previous solution can be bad. However, we can obviate the problem and attain robustness thanks to known results of Mahdian et al. [012]] and Meyerson 2001].
Corollary 3.1.1. Let P and S be as in the statement of Theorem an online randomized algorithm whose expected cost is at most,
3.1 and let n = [P]. Then, there
log(n) log log(n)
o min log((S)) OPT(P.S),
OPT
Corollary 3.1.1 is direct application of the results of Mahdian et al.
20122. and shows that
our algorithm is comparable to the true offline optimum of the problem. Therefore, we focus on
Theorem 3.1 from now on and we present the proof of Corollary 3.1.1 with the full description of the algorithm in the Supplementary Material.
Intuitively, we are going to implement the following reduction. The initial problem is to find good facilities, taken from the set S, for an online sequence of points P == {pi..... Pn }- Instead, we will find facilities for the sequence of "nearby" points Q := {9p, ................................ 9p. 1. where 9p is the point of S closest to p. Recall that, since S is a metric space, there an HST family (T. D) for it. By construction, the leaves of every T E T are the facilities in S. To find good facilities for Q. we will pick tree T TT randomly according to DD once and for all and use to find good facilities for the entire sequence Q. When a request for 4p arrives, we return (hopefully) good leaf of T. In choosing the leaf, we work with the distance dr induced by the tree which is (in expectation) good approximation of the distance d in the metric space. And so, good solution in the metric induced by T' is also going to be (in expectation) a good solution in the original metric space. The advantage of using 7 relies on the strong structural properties of HSTs. Note that the sequence Q may contain repeated points even when the input sequence P does not. Known online algorithms do not seem to be able to cope with this situation in a satisfactory way. Indeed, in Section 4 we prove lower bound that rules out Meyerson's algorithm as well as other well-known algorithms, motivating our HST-based approach.
The core of the solution is algorithm PLUCK which finds a good facility for p's proxy Up- To find facilities for the whole input sequence, PL.CK is called repeatedly by procedure TAKEHEeD. The input to TAKEHEED are the sequence of clients P from metric space (X, d). the set S of suggested facilities, and an HST family (T, D) for the metric space (S, d) induced by S.
Algorithm 1 Algorithm TAKEHEED
1: Pick T at random from the HST family D).
2: When a point p arrives, let qa E be its closest suggested facility.
3: Call PLUCK with input qp. and rTo: assign the returned facility Ep to p.
It remains to define PLUCK. Its input consists of point 9p E S S, an HST tree T above, and node u E T. initially set to the root of T (so, effectively, we can say that its input consists of 9p and T). The output is leaf & E T. Starting from the root, PLUCK goes down the tree T recursively in search of a good leaf for qp- Once the leaf is found it is opened and returned. The tree T is passed "by reference" so that: once a leaf is opened, it remains open during all future invocations of PL.CK. Initially, no leaf is open. Every node in the tree T has a potential, initially set to zero. The potentials too are modified "by reference" and are preserved from one invocation of PLUCK to the next. In Algorithm 2 we give the pseudo-code for PLUCK. The main goal of PLUCK is to serve the newly arrived client with a facility within distance f from 4p. with the additional guarantee that not too
We develop another Algorithm, BUCKETHEED, which does not merge together all the advice sets, but assigns them to different "buckets" depending on their cardinality. In this way. it produces a solution with quality not depending on SS), but on the size of the best advice. See the Supplementary Material for more details.
5

---

many facilities are opened by successive executions of the algorithm. To achieve this goal PLUCK operates as follows. If there is no open facility within distance f from qr- PLUCK opens a new facility within distance f/a from fp- In so doing, it selects the facility that is able to serve the largest number of future clients (see subroutine SELFECTHFAVTESTCHHIDD if and only if the potential of an internal node is higher than the cost of opening a facility. Intuitively, this guarantees that we do not open too many facilities because: in the former case we reduce the number of possible points without facilities within distance f substantially; in the latter, we can charge the opening cost of the facility to the serving cost the instance.
Otherwise, PL.CK opens a new facility
Algorithm 2 Algorithm PLUCK((T, v1
Input: HST tree T, node v T, point q E S Output: leaf of T
1: if v is a leaf of then
2: open v (if already opened, do nothing)
3: return
4: Let he the sub-tree rooted
5: if (T)) has no opened leaf within dist. f from q then
6: ur = BELLECTHEAVVVSSCHI..D.. 9,9)
7: return PLUCK(T, w,,9 9)
8: else
9: Let x: be the child e s.t. is a leaf of T(r)
10: if (x)) contains an opened leaf then
11:
return PLUCK(T, x.
12:
else
13:
Select the child y of T(y) contains the opened leaf closest & (ties broken arbitrarily) Increase x's 's potential by (9: E) if the new potential exceeds the cost f of opening a facility then
14:
15:
16:
return PLUCK(T, xx,
17:
else return! !
PLUCK is well-defined and it always terminates (see the Supplementary Material for formal proof).
Notation 3.1. For every 4p and tree T, PLUCK returns leaf. denoted from now as tp which is the facility associated to the point (recall that the leaves of are the set of suggested facilities)..
Furthermore, note that ép is always at tree distance no greater than f from qp. i.e. dr(qp: Ep) S f. And, if t, is opened input 9p by the invocation of SELECTHEAAIESTCHHDD then dr (qp: (p) S 1/3.
Algorithm 3 Algorithm SELECCTHEAAIESTCCIIDDDD v.
Input: an HST tree T, node E T, and a point q S
Output: child of in T
return w such that: (i) w is a child of o:
(ii) T(w) has a Icaf at distance no greater than f/3 from g.
(1i7) the number of leaves of T(w) is maximum (among those satisfying (ii), breaking ties arbitrarily)
3.1 Algorithm Analysis
All the proofs have been moved to the Supplementary Material for lack of space. However, here we recreate the workflow of the proof of Theorem 3.1 To establish 3.. fix an optimal
solution restricted to S, F == {c] {ci.-.., <t C S, and compare it to the solution returned by TAKEHEED. The optimal solution naturally induces a clustering of the clients C- == [Ci,....... Ci..
where CF := {p E P o is the facility in J closest to topp) }.
Notation 3.2. Let ct denote from now on the facility in the optimal solution closest to point p. And let K* denote the number of facilities opened by the optimal solution.
In what follows, we establish series of bounds that hold for every tree T E T in the HST family. Once this is done, we invoke linearity expectation to obtain the desired bound. Recall that is the distance in the original metric space while dr is the metric induced by tree T E T. We start with two useful lemmas. The first says that we can bound the service cost of a point p with that of its proxy 4p in the tree metric dr. The second relies on the properties of HSTs.

---

Lemma 3.2. Let T E T. Then, d(p, S c(p,cc) + dr(4p, 4p).
Lemma 3.3. Er~D(dr (gp. (pp)))))])))))).){) I 16 logg(()))dppc))
Hence, to bound the cost d(p, Ep) for point p. need to find bridge between dr (gp. lp) and dr (9p (9p. s)) We now partition the clients into two groups, those that are "far" from the optimal centers and those that are "near": P := {p E P dr dr(pp- c,) S 5/6} and P := P P NDAK
Notation 3.3. Let é be the opened facility returned by PLUCK on input qy If this is the first time the leaf was opened, we assign the entire facility cost f to Otherwise, we assign zero. Let f (p) denote the facility cost assigned by this mechanism.
Given that T is fixed in our analysis and there is no ambiguity, we will drop the superscript T for notational convenience. The cost incurred by far away points can be easily bounded through point-wise bounds, following by the definition of PEAR.
Lemma 3.4.
Σ PEPPAR
(d((a 6p) + ((0))
S 12 Σ drlups Cp)
pEPPAR
We can focus on NEEA from now on, for which the proof's get more involved. In Lemma 3.2 we bounded the service cost incurred by the algorithm for each point p with its optimal cost and the distance between the proxy 9p and the facility Ep. We now do the same for the facility cost.
Lemma 3.5. Let TT
E Pe PNEAR
S
E PEP
dr ep) + fk
to close the circle we need to relate dy (4p / 6p) to dr (gps :)) Technically this is the most challenging step, achieved by the next lemma which requires careful use of the properties of PLUCK.
In view of Lemmas 3.2 3.3 and 3.5
Lemma 3.6.
Σ dr(qp: kp) s 2fk log((8)) +4 Σ dr dgp cp).
PEPNEAR
PEPNEAR
By combining Lemmas 3.4
3.6 a similar bound for the facility costs can be established.
Lemma 3.7. Let T T. Then.
Σ (61og( + 1)fk* + 18 Σ dr(gp: cg)-
PEPNEAR
All the pieces can be assembled prove Theorem 3.1 (see the Supplementary Material).
4 Lower Bounds
In this section we present two lower bounds whose proof is deferred to the Supplementary Material. The first shows the approximation guarantee of Theorem to be almost optimal. The second shows that, in the worst case, [Myerron [200]]ss II well-known algorithm computes solution whose cost is Q([] OPT(S)). as opposed the (ggg(( OPT(S)) bound of Theorem 3.1 The same is also true for the algorithms from Fotakis 20033 2005). This provides strong motivation for our HST approach.
Theorem 4.1. Let f = 1 he the uniform facility cost. For every k ' 1, there exist a metric space, sets of facilities S [k),, (with |s| [[e[N) S = k)) and probability distribution over the input sequences such that, when an imput sequence P is generated according to this distribution: (i) with
probability 1, min COST(P, (P, S.) (1) (i.e. one of the sets suggests a solution of cost O(1) log [S]
and yet, (ii) no online algorithm can provide a solution of expected cost smaller than
log log (S
We now proceed by defining general class of algorithms for online facility location.
7

---

Table For the real datasets, an instance consists of the activities of one day. To obtain an input for the algorithm an instance is paired with facility cost.
Dataset
# Instances
Median size
Size range
Mixtures
750
5, 000
1, 1,000- 10, 000 5 140 39 25, 125
Brightkite
901
3. 119
Gowalla
388
9,355
Uber
183
24, 550
10, 202 43, 205
Definition 4.1. An algorithm for online facility location is said to be "Meyerson-like" if only opens facilities at previously seen input points.
Notice that the algorithms from Meyerson 2001 Fotakis
2003 are Meyerson-like according to
Definition 4.1 while the algorithms by Anagnostopoulos et al. 2004
Fotakis (2005) are not.
Theorem 4.2. Let f= 1 be the uniform facility cost. For every integer k > O, there is finite metric space (S, d) of cardinality SS = and input sequences such that: (i) The optimal solution has cost O(1), but (ii) Any Meyerson-like algorithm computes solutions of cost ((((S)) (2(k); (ii) SNFL algorithm from from Fotakis 2 computes solutions of cost 92( ((S) = (1k)).
Notice that ||| = 1e is not the size of the input, which could contain repeated points of S, these lower bounds have nothing to do with the logarithmic lower bound from Fotakis (2003). Theorem 442 further validates our approach, since it rules out any Meyerson-like algorithm. which include many online algorithms for facility location, and SNFL algorithm from Fotakis (2005) too. On the other side, we manage to bypass this lower bound by considering as candidate facilities also points from the advice, and exploiting HST's to identify the limit point in a subset of the facilities.
5 Experiments
We studied the performance of TAKEHEED with real-world and synthetic datasets by comparing against the state of the art online algorithms of Meyerson [2001]. Fotakis (2003), And/Anggossoopollos al. [2004). For all algorithms above we used our own implementation Note that the first algorithm randomized, as it is TAKEHEED. To generate the trees of the HST families we implemented the algorithm of Fakcharoenphol et al. [004]].
As baseline to compare against we use the 1.22-approximation algorithm for offline facility location by |ahdiia et al. [2002), referred as THEBASELINE the sequel. For it, we used the Max Planck Institute implementation [Hoefer] 22022]
To test robustness, we use the algorithm of Mahdian et al. 2012 This algorithm accepts in input two algorithms and mixes them in a way as to ensure that cost of its output is always of the same order of magnitude of the better of the two. The algorithm can also mix a set of points (i.e. advice) with algorithm, or two sets of points.
For synthetic instances, we sampled points from a mixture of Gaussians (from 10 to 100) having centers in [0. 1]2 and variance scaled by the number of mixtures. The metric is the euclidean distance. For real real-world datasets, we consider Gowalla and Brightkite, from the SNAP Dataset Collec- tion [Leskovec and Krevi 2014). and Uber longitude, and timestamp of some activity: check-in from the location-basee social networks (Cho et 2011 for the first two (restricted to the US), and pickups in New York City for Uber. For each dataset, an input instance consists of all such activities that occurred in a given day, sorted by timestamp. The metric used is the great-circle distance in kilometers. Table L gives additional information on the datasets.
Eight 2015). Each of these contains latitude,
For every input instance, all randomized algorithms were run 10 times. The plots report the average and variance of the cost of their solutions. All experiments ran on desktop computer.
Synthetic Instances. The input sequence and the advice were generated as follows. First, set of N points was sampled from the mixture of Gaussians. The input sequence consisted of these points in random order. The advice was obtained as follows. THEBBSELINE was given the random set in
http:///tttaaccaaaooooogggiaaaae -tt.raatiiiootttt-----ieeeeeeeeo Xultiple-Advice
with

---

ABUV
Pat
Tahelleed
RawAdvice
ABUV
Takeleed
Raw.Advice
2.4
Compattion Rato
1.8
Compettivve Ratio
M/4
1.6
1.6
1.4
1.2
1.2
1.0
2.0
4.0
8.0
16.0
32.0
64.0
128.0
100
200
300
400
5:00
600
700
800
900
Day
Figure 1: Average estimated competitive ratios on Gaussian mixtures (5000 points from 50 Gaus- sians) with noisy advice. The shaded area repre- sents one standard deviation.
Figure 2: Average estimated competitive ratios on Brightkite with f 1000. The shaded area represents one standard deviation.
input and produced set of M facilities output. Then, M additional random points were added. Finally, the 2M points were randomly partitioned into 5 sets of equal size. In the experiments, for every mixture, 50 random instances were generated.
Weal-World Instances. For real-world datasets, we divided every day into four consecutive time windows of hours each, starting from midnight. An input sequence consisted of all the points (activities) of given day. The multiple advice was obtained by running THEBASELINE on each time window of the two previous days, for a total sets of suggested facilities. In this way, we were able to obtain multiple advice containing both bad and good suggestions. For every input sequence, we tried different values of f, the facility cost. Changing f did not affect the outcome terms of performance comparison. The results we show exemplify the general picture. Likewise, we ran all the randomized algorithms using different seeds. Again, this had no discernible consequence on the performance.
Raw advice. The previous discussion describes how multiple advice was generated. Algo- rithm RAWADVICE provides a useful baseline to quantify its quality. It operates as follows. Given the union of the facility sets comprising the advice, each client in the input sequence is assigned the closest facility, which is opened. The cost of this solution gives a useful quantitative indication of how good the multiple advice is. In principle, the algorithm of Mahdian to mix the sets. By generalizing the mixing process, it is possible to work with multiple algorithms, switching to the rest-performing one for each arriving client. In practice, however, just taking the union gives the best result. This is true for both the normal and robust versions of the algorithm. So we focus only on the approach merging all the suggestions in what follows.
al. [2012] gives another way
Preprocessing. The performance of TAKEHEED hinges upon the tree sampled from the HST family (recall that we used the algorithm from Fa Takeharoenphol et al. (0044). ). Recall that the points of the multiple advice induce a metric space for which an HST family exists. To improve performance, we sampled several trees (10 and 100, respectively, for real and synthetic datasets) and picked the one that minimized distortion The distortion was computed naively, as the maximum over all the pairs of points, with no attempt at optimization. Even so, the preprocessing time was negligible. We do not report exact figures because here we are only concerned with the cost of the solutions.
Outcome. In the sequel we use the term competitive ratio in the following sense: the competitive ratio of algorithm X is the ratio between the cost of the solution given by X and that of T'THEBSSELNE. This gives uniform measure of comparison. For Fotakis and ABUV algorithms, which are parametrized, we tried different values for the parameters and report here only the best ones.
Synthetic Instances. In Figure I we report the results synthetic instances. Note that the number of opened facilities for large values of f the opening cost becomes small and the difference in behavior between TAKRHERD and RAAADVIC decreases. In presence of noisy advice, TaKeHeed consistently outperforms both the other online algorithms and the naive use of the advice. Similar results obtained for different numbers of Gaussian mixtures.
the ratio between the metric space distance and the distance, for the worst pair of points.

---

ABUV
For
Wary
Sturdy
ABUV
RawAduice
2.50
Mey
Takefleed
Waay
Compettire Rato
2.25
Compottive Rati
2.5-
2,00
1.75
1.50
1.5
1.25
300
900
Day
Day
Day
Figure 3: Average estimated competitive ratios of the robust variants and the baselines on Brightkite with f = 1000. The shaded area represents one standard deviation.
Figure 4: Detail of 2 and around some extreme instances (not smooth). The robust versions man- age to recover from bad advice.
WorldW Instances. In Figure 2 we compare TAKEHEED with the competitors for the Brightkite dataset. Similar results were obtained with all datasets (see the Supplementary Material). The facility cost was determined in such a way that THEBASELINE opened a number of facilities between I 1%-10% of the number of input points. TAKEHEED always outperforms all other algorithms, except for one outlier instance, to which we return (see the spike occurring around day = 525 of the plot). This good behavior was consistent across all datasets, illustrating the interesting fact that high-quality multiple advice might be cheaply and consistently produced.
Robustness. As mentioned, robust online algorithms can be obtained by using the mixing algorithm of Mahdiaa et al. 2012).. Algorithm WARY is obtained by mixing our TAKEHeed with Meyerson's 's algorithm. While algorithm STURDY is obtained by simply mixing Meyerson's 's algorithm with the advice set. The mixing algorithm has a parameter 7 with which one can give more weight to one of the components to be mixed. We show the outcome for ? 1.75 which gave best results (7 treats them equally, while = 1.75 gives less weight to Meyerson's 's algorithm). An in-depth analysis of the role of this parameter is given in the Supplementary Material.
Figure reports the outcome for the same Brightkite dataset, while Figure zeroes in on the spike of Figure 2 The latter illustrates how the robustness plays out when the advice bad. While TAKEHEED suffers from receiving a bad advice, its robust counterpart WARY does as well as the best online algorithms using no advice, as predicted by the theory. Different values of the facility cost produced the same outcome.
Conclusion
We introduced TAKEHEED, WARY, and BUCKETHEED, three online algorithms for online facility location that take advantage in different ways of multiple advice - i.e. advice coming from disparate sources possibly containing noise and misleading information. The algorithms exhibit good theoretical guarantees as well as good practical performance. Our approach also illustrates that high-qualin, multiple advice might be easy and inexpensive to obtain in practical situations, giving rise to algorithms that can outperform online algorithms that heed no advice. In those seemingly rare occasions in which good advice not possible to obtain, WARY, the robust version of TEKEHEEd, has been shown to be able to disregard the poor advice and perform well as the best online algorithms. We consider our results as case study a more general philosophy that appears to be promising approach to tackle large variety of interesting problems.
Acknowledgements
This work was supported in part by Google Focused Research Award, by the PRIN project 2017K7XPAN, by BiCi Bertinoro international Center for informatics, and by the MIUR under grant "Dipartimenti di eccellenza 2018-2022" of the Department of Computer Science of Sapienza University.
10

---

References
Charu Aggarwal and Chandan K Reddy. Data clustering. Algorithms and applications. Chap- Hal/CCCCCCCC Data mining and Knowledge Discovery series, Londra, 2014.
Abu Reyan Ahmed, Md Saidur Rahman, and Stephen Kobourov. Online facility assignment. Theoret- ical Computer Science, 806:455 -67, 2020.
Aris Anagnostopoulos, Russell Bent, Eli Upfal. and Pascal Van Hentenryck. A simple and deter- ministic competitive algorithm for online facility location. Information and Computation, 194(2): 175-202, 2004.
Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science, pages 184-193. IEEE, 1996.
Allan Borodin and Ran El-Yaniv. Online compulation and competitive analysis. cambridge university press, 2005.
Joan Boyar, Lene M Favrholdt, Christian Kudahl, Kim S Larsen, and Jesper W Mikkelsen. Online algorithms with advice: A survey, ACM Computing Surveys (CSUR), 50(2):19, 2017.
Eunjoon Cho, Seth A Myers, and Jure Leskovec. Friendship and mobility: user movement in location- based social networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1082-1090. ACM, 2011.
Anna Choromanska and Claire Monteleoni. Online clustering with experts. In Artificial Intelligence and Statistics, pages 227-235. PMLR, 2012.
Vincent Coden-Addad, Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. Advances in Neural Informa- tion Processing Systems, pages 3250-3260, 2019.
Vincent Coden-Addad, Benjamin Guedj, Varun Kanade, and Guy Rom. Online k-means clustering. In International Conference on Artificial Intelligence and Statistics, pages 1136-1134. PMLR, 2021.
Marek Cygan, Artur Czumaj. Marein Mucha, and Piotr Sankowski. Online facility location with deletions. In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik, 2018
Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. arXiv preprint arXiv:201 2020.
Jittat Fakcharoenphol. Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3)485-497, 2004 2004.
FiveThirtyEight. Uber pickups in new york -uber-pickus--in- now-- city 2015.
Dimitris Fotakis. On the competitive ratio for online facility location. In International Colloquium on Automata, Languages, and Programming, pages 637-652. Springer, 2003.
Dimitris Fotakis. A primal-dual algorithm for online non-uniform facility location. Panayiotis Bozanis and Elias N. Houstis, editors, Advances in Informatics, pages 47-56, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
Dimitris Fotakis. Online and incremental algorithms for facility location. SIGACT News, 42(1):
97-131, March 2011. ISSN 0163-5700. doi: 10.1145/1959045.19555 1959065..
Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris. Learning augmented online facility location. arXiv preprint arXiv:2107.08277, 2021.
Guojun Gan, Chaoqun Ma, and Jianhong Wu. Data clustering: theory, algorithms, and applications. SIAM, 2020.

---

Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228 248, 1999. ISSN 0196-6774. doi: https://doi.org// wttp://i..or///...0////////gg// 1006///0m...998.. 0993.
Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. On the facility location problem in online and dynamic models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagstubl--LiinnzzZzznne Zentrrum für Informatik, 2020.
Martin Hoefer. Performance of heuristic and approximation algorithms for the uncapacitated facil- ity location problem. Research Report MPI-I-2002-1-000 Stublsatzenhausweg 85, 66123 Saarbrücken, Germany, December 2002.
Pea--ll-lnsstttttt für Informatik,
Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019.
Anil K Jain and Richard C Dubes, Algorithms clustering data. Prentice-Hall, Inc., 1988.
Shaofeng H. C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang. and Yubo Zhang. Online facility location with predictions. arXiv preprint arXiv:2 (0.008440008840, 10.08840, 2021.
Bernhard Korte and Jens Vygen. Facility Location, pages 629 Springer Berlin Heidelberg, Berlin, Heidelberg, 2018.
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pages 489-504. ACM, 2018.
Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In Proceedings of the 34th Interna- lional Conference on Machine Learning-Volen Volume 70, pages 1975-1984. JMLR. org, 2017.
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection, June 2014.
Shi Li. A L.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45- -5., 2013. ISSN 0890-5401. doi: itt.://i..rr/....111..........o. 58, 007. 38th International Colloquium on Automata, Languages and Programming (ICALP 2011).
Edo Liberty, Ram Sriharsha, and Maxim Sviridenko. An algorithm for online k-means clustering. In 2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX), pages 81-89. SIAM, 2016
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. arXiv preprint 1xX.:v1802.005330 2018
Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang. Improved approximation algorithms for metric facility location problems. In International Workshop on Approximation Algorithms for Combina- forial Optimization, pages 229-242. Springer, 2002.
Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncertain information. ACM Transactions on Algorithms (TALG), 8(1):1-29, 2012.
Andrew McGregor. Graph stream algorithms: survey. ACM SIGMOD Record, 43(1):9-22 20, 2014.
Andrés Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid pre- dictions. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1856-1864. Curran Associates Inc., 2017.
Ramgopal Mett and Greg Plaxton. The online median problem. SIAM Journal on Computing, ((13):16-883)) 2003.
12

---

A. Meyerson. Online facility location. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS '01, page 426, USA, 2001. IEEE Computer Society. ISBN 0769513905.
Vahab S Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Simultaneous approxima- tions for adversarial and stochastic online budgeted allocation. In Proceedings of the twenty-third anmual ACM-SIAM -SAM symposium on Discrete Algorithms, pages 1690-1701. Society for Industrial and Applied Mathematics, 2012.
Michael Mitzenmacher. A model for learned bloom filters and related structures. arXiv preprint arXiv: 2018.
Michael Mitzenmacher.
Scheduling with predictions and the price of misprediction. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz Zentrum für Informatik, 2020.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint arXiv:2006.099 010.0.9992200 123, 2020.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018.
Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1834-1845. SIAM, 2020.
Alexander Wei. Better and simpler 1377: 2020.
online caching.
arXiv preprint
Jian Zhang, Zoubin Ghahramani, and Yiming Yang. A probabilistic model for online document clustering with application to novelty detection. Advances neural information processing systems, 17:1617-1624, 2004.
13


Reviews:
[{"review_id": "e1GIIBSvHi", "reviewer": "Reviewer_ueSN", "summary": "The paper studies the problem of online (uniform) facility location with multiple expert advices. Here the expert advices are given in the form of the offline optimal facility set: i.e., each advice is a set of facilities that are claimed to be open by OPT. The main result of the paper is an algorithm with cost $O(\\log(|S|))\\mathrm{OPT}(S)$, where $S$ is the *union* of all the expert advices, and $\\mathrm{OPT}(S)$ is the best (offline) cost one may get by using only facilities from $S$. By combining with known worst-case online algorithms (e.g. Meyerson's algorithm) using standard blackbox method, one easily get an algorithm with robustness-consistency performance guarantee.\n\nThe main idea of the $O(\\log|S|)\\mathrm{OPT}(S)$-cost algorithm is to first embed the facility set to an HST, then run an alg similar to Meyerson/Fotakis, except for one important difference: when the algorithm decides to open a facility in some region, it (Algorithm 3) choose to open the \"limit point\" in that region rather than the facility giving smaller cost. In particular, this difference enables the algorithm to circumvent the classical lower bound instance given by [Meyerson'01]: the instance consists of a sequence of clients that converges to a point in the space.\n\nFinally, notice that since the goal is to approximate $\\mathrm{OPT}(S)$, one can w.l.o.g. move all clients to the location of $S$ losing only an additional $O(1)$ factor. Then using similar argument as in [Fotakis'11] one can get the $O(\\log|S|)*\\mathrm{OPT}(S)$ cost, which could be better than the $O(\\log n)$-apx of Meyerson/Fotakis when $\\mathrm{OPT}(S)$ is close to OPT.", "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": "**[Strength]**\nI think the main contribution is the $O(\\log|S|)*\\mathrm{OPT}(S)$-cost algorithm, while the rest part is rather standard. I like the idea of using HST to identify the limit point in (a subset of) the facilities. Simple but clever. The result is also interesting even without the learning-augmented background: it implies better competitive ratio when the facilities come from a fixed set (that's much smaller than potential client sets), which is often the case in practice. The authors also provide a lower bound (almost) matched by their algorithm. I don't have time to look at the experiments, but I think it's not important for the evaluation of this paper.\n\n**[Weakness]**\nAlthough the lower bound Theorem 4.1 is incomparable with that given by [Fotakis'03], it is not hard to obtain by a small modification. In fact the lower bound construction given in the paper is almost identical with that of [Fotakis03].\nFinally, the author should discuss a little bit more on the primal-dual algorithm by [Fotakis'05], which is not \"Meyerson-like\" and thus Theorem 4.2 does not directly apply.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "cXGYHlnRcYm", "reviewer": "Reviewer_b1z8", "summary": "The paper studies the online facility location problem in a setting where you have multiple advice in the form of a set of lists of suggested facilities to open. They introduce an algorithm that they show to competes with the best possible algorithm for online facility location even when the advice is bad and outperforms the best possible when the advice is good.", "questions": "", "limitations": "", "rating": 7, "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 paper is well written and is well structured. The arguments seem to follow clearly and the structure of the arguments is clearly laid out. The paper uses the structural properties of HSTs to design and analyze a robust framework for the online facility location with advice. It seems that the advice in this setting could be adversarial. But since the advice does not change over time, the adversary is non-adaptive. I know this is out of the scope of the paper, but is it possible to say anything about what might happen if you are allowed to change some $\\epsilon/n$ fraction of the advice at each time? Could this be counted towards bad advice and the robustness arguments used to say that even in this case the performance is good? Feel free to skip this question if you have to, as it is out of the scope. Also, what is the significance of Wary against Robust-Takeheed, if the best possible advice set is also an adversarial set that is large (something like $\\epsilon n /k$) how would the two approaches compare? Also, how does $OPT(P,S)$ compare against the true optimal (could this cause any additional $S$ factors especially pertaining to the lower bound analysis)? Also, is there a formal definition of bad advice?\n\nOn the formatting front, it might be nice to have the pluck algorithm in a single column as double columns make it hard to compare some structural properties, i.e. indentation making it slightly harder to read. This is just a suggestion as it is not a major issue anyway. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The advice setting in the paper while being adversarial, is not allowed to change after the initial selection though this is simply the framework considered for the scope of the paper. Also, the bounds in the paper are derived against the optimal solution restricted to $S$ and it is not clear how it compares against the true optimal. The concept of bad advice seems to be loosely defined.\n\nAs the problem itself is a classical problem I don’t think it creates any major negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "No major ethical concerns as far as I can see.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Xbh1FNEXuFR", "reviewer": "Reviewer_GcD7", "summary": "The paper looks at the problem of online facility location with multiple advice.\n\nIn the online facility location problem points of a metric space arrive online and once a point arrives it either has to be connected to an already open facility, or a new facility gets opened to serve it. These decisions are irrevocable and the goal is to minimise the total cost which consists of the cost for opening the set of facilities and the sum of distances from each point to the facility that serves it. The best known algorithm for the problem is due to Fotakis and obtains a competitive ratio of $O(\\log(n)/\\log\\log(n))$. \n\nThe current paper assumes that the algorithm has obtained $k$ different sets of points as \"advice\". Each such set of points $S_i$ can be thought to represent a set of suggested facilities to open, but it is unclear which -- if any -- of these sets lead to a good solution and which not. The paper uses this advice to develop algorithm TakeHeed with expected cost $O(\\log|S|)\\cdot OPT(S)$, where $S$ is the union of advice sets and $OPT(S)$ the best solution among the ones that are restricted to use facilities of $S$. Clearly, $OPT(S)$ cannot be worse than the optimal solution restricted to each advice set, so intuitively the algorithm is good when there are relatively few points in the advice sets and at least one of them is reasonably accurate. The algorithm can be robustified by standard techniques (Mahdian et al.) and an additional algorithm is given in the supplementary material for the (arguably not so natural case) in which $|S|$ is large. This additional algorithms compares directly to the quality of the best advice set.\n\nThe paper also contains expermints both on synthetic and real world (albeit from different settings) inputs.", "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": "Algorithm TakeHeed builds upon hierarchically separable trees and, although quite involved and non-trivial, is elegant at the same time. Furthermore the paper is really well written and the clustering problem that is studied is very interesting.\n\nThat being said, I have two concerns regarding the paper:\n\n1. I am not fully convinced with the multiple predictions model. I would consider it more natural to have one predicted set of facilities to open and to give the competitive ratio as a function of the error (some distance measure between the predicted set and the actual optimal set of facilities). The choice of multiple predictions model seems also a bit strange given that, at least as far as I can tell, it is the union of the predicted sets that is used in the algorithm (and on top of that, that also appears in the performance guarantee of the algorithm). Although the additional algorithm actually works with individual prediction sets it is again not clear how to compare it to the best algorithm without predictions (see concern (2.) below).\n\n2. the performance of the algorithm is given with respect to cost of the algorithm and not with respect to the competitive ratio which makes it quite hard to compare the theoretical result to other algorithms. In particular the given costs may depend among other things on the number of facilities in a predicted or optimal solution.\n\nFinally, the experimental results are quite interesting in that they (i) support the belief that such multiple advice sets can indeed be obtained from historical data, and (ii) show that the algorithm actually outperforms other algorithms. So although I think that the prediction model is not the most natural, and the theoretical results are maybe not as meaningful to interpret as a performance guarantee, it seems that at least in practice the algorithm performs reasonably well.\n\nI think that the paper is slightly above borderline but would be more than happy to reconsider my score after the rebuttal of the paper.\n\nSome minor notes for the authors:\n- The algorithm naming is a bit unfortunate, in particular since the robustified version of TakeHeed is called Wary, but a different algorithm is called Robust-TakeHeed.\n- On line 62 you talk about the performance guarantee, but what you write is actually the cost of the algorithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no limitations or social impact concerns.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Wzxm4uKWgvO", "reviewer": "Reviewer_gYHr", "summary": "This paper is about online algorithms augmented with predictions of the future input. In particular, the authors examine the problem of online facility location. In the classical version of this problem, there is a sequence of points in a metric space that arrive in an online fashion and represent the location of a client. The algorithm has to irrevocably decide to either connect each of those clients to an existing facility paying some “service cost” proportional to the distance from it, or a new one that would incur an additional “facility cost” $f$ to be created. \nThe authors here consider a version of the problem where the algorithm is provided with advice from multiple sources. Each piece of advice $S_i$ consists of a set of points where the optimal locations of the facilities are predicted to be. The first algorithm proposed uses the union of those predictions $\\mathcal{S}=\\cup_i \\{S_i\\}$ and incurs a cost which scales proportionally to $\\log|\\mathcal{S}|$ and the optimal cost given that only facilities in $\\mathcal{S}$ can be used. \nThe algorithm and its proof is quite technical and makes use of hierarchically separated trees, that had been also used in the classical version of this problem. Matching lower bounds up to a $\\log\\log |\\mathcal{S}|$ factor are also provided as well as experimental results to compare with prior work. \n", "questions": "", "limitations": "", "rating": 5, "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 looking at a very important classical online algorithms problem from a novel perspective, and got some interesting both positive and negative results. However, the theoretical part seems to be a bit lacking because the cost of the algorithm is not compared to the offline optimal cost, but rather to the optimal cost given that the facilities can only be opened in a location that has been predicted. Thus, this is equal to the offline optimal cost only if the union of the prediction sets contains all optimal locations for facilities. I think an attempt need to be made to relate the cost of the algorithm to the offline optimal algorithm, as it is the standard for online algorithms. Additionally, the presentation could also be improved. For example, Algorithm \"TakeHeed\" only uses the union of the advice sets and therefore some statements could be simplified. If I understand correctly, the separate advice sets are only relevant for \"Robust-TakeHeed\", which is not described in the main body of the paper. \n\n\nComments:\n- Line 124: the variable $k$ is overloaded here. It has already been used for the number of advice sets and this could create confusion. \n- Theorem 3.1: This theorem should probably be rephrased such that the advice is a single set $\\mathcal{S}$ and is can just be applied on $\\mathcal{S}=\\cup_i \\{S_i\\}$ when needed, since the separate sets $S_k$ are not used.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors as well as myself do not see any potential negative societal impact from this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a learning-augmented algorithm for online facility location. The competitive ratio of the algorithm depends on the quality of the prediction, and the size of the advice; it is never worse than the competitive ratio of the best worst-case algorithm. 
There was a substantial debate about (i) the advice model - how natural/realistic it is and (ii) the approximation guarantees, esp. the possible discrepancy between OPT and OPT(P,S). Overall, however, the reviewers felt that these issues do not significantly reduce the value of the paper.

Decision: Accept (Poster)