Learning from a Sample in Online Algorithms
Authors: C.J. Argue
Alan Frieze
Anupam Gupta
Christopher Seiler
Venue: NeurIPS 2022 Accept (2022)
Keywords: Learning Augmented Algorithms
Online Algorithms
Sample Complexity
Load Balancing
Optimization
Steiner tree
Facility Location
Clustering

Abstract:   We consider three central problems in optimization: the restricted
  assignment load-balancing problem, the Steiner tree network design
  problem, and facility location clustering. We consider the online
  setting, where the input arrives over time, and irrevocable decisions
  must be made without knowledge of the future.
  For all these problems, any online algorithm must incur a cost that is
  approximately $\log |I|$ times the optimal cost in the worst-case,
  where $|I|$ is the length of the input. But can we go beyond the
  worst-case?  In this work we give algorithms that perform substantially
  better when a $p$-fraction of the input is given as a sample: the
  algorithm use this sample to \emph{learn} a good strategy to use
  for the rest of the input.


Learning from a Sample in Online Algorithms
C.J. Argue
Alan M. Frieze Anupam Gupta
Christopher Seiler
Departments Computer Science and Mathematics Carnegie Mellon University
Pittsburgh, PA 15213
Abstract
We consider three central problems in optimization: the restricted assignment loa-bbllnninng problem, the Steiner tree network design problem, and facility lo- cation clustering. We consider the online setting, where the input arrives over time, and irrevocable decisions must be made without knowledge of the future. For all these problems, any online algorithm must incur cost that approxi- mately log | times the optimal cost in the worst-case, where |7] is the length of the input. But can we go beyond the worst-case? In this work we give algorithms that perform substantially better when p-fraction of the input is given as a ple: the algorithm use this sample to learn a good strategy to use for the rest the input.
Introduction
The area of sequential decision-makinn (a.k.a. online algorithms) is central direction in algorithms under uncertainty: faced with a sequence of requests arriving over time, an algorithm needs to make decisions without knowing the future. Given this lack of information, how can make near-optimal decisions? An enormous amount of work has been done on problems in this area over the past decades, and we know near-optimal worst-case bounds for many problems of interest in clustering, online resource allocation, scheduling, and network design.
However, these worst-case bounds often pessimistic (perhaps by definition): they focus the hardest, pathological instances. Can we give algorithms that work for instances that arise in practice, which tend to be very far from the worst case? There have been many attempts to formalize this question: see the textbook by Roughgarden [2020] for several approaches to go beyond the worst- case.
In this paper we focus on online algorithms with a sample (AOS) framework of Kaplan et al. [2020, 2022]: similar model was defined by Lattanzi al. [2021] based on Kumar al. [2019]. In this model, we assume that an arbitrary instance / is chosen, perhaps by an adversary. A random sample S containing a p-fraction of the instance is then presented to the algorithm, phase". Having used this sample to learn something about J, the algorithm faces the rest of the instance T \ S (in its adversary-chosen order). This is essentially the "testing phase". The algorithm needs to service these requests, and ensure that for each input
part of "training
Egl cost of algorithm A on < g()) Eæl optimal cost for R..
(1)
Here the expectation is taken over both the p-random sample S (and hence its complement Rt), as well over the internal randomness of the algorithm A. Can we design algorithms that use this small random sample (just an p fraction) to extract enough information substantially improve its performance?
We show the answer is "yes" for three combinatorial optimization problems in load- head-balancing clus- tering, and network design:
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1. Load-Bale -and-Balaniing: Jobs arrive over time; each job j can be assigned to one of some subset Nj) S [m]] of some m fixed machines. Minimize the maximum load of any machine.
2. Clustering: In facility location, clients arrive in a metric space, and we want to cluster them (and open one facility in each cluster). Minimize the total cost to open facilities and connect clients to them.
3. Network Design: In Steiner tree, points of a metric space arrive one by one, and need to be connected up to form a spanning tree. Minimize the total length of the tree edges.
All three problems have been studied in the worst-case setting, where it is known that for any online algorithm there are instances where the algorithm's 's cost must be least = Qllog [7] factor larger than the optimal cost; here [/] is the size of the instance. In this paper we want guarantees which do not depend on the instance size [ but only the fraction p of the input in the sample.
Our Contributions. Our main results are that given an p-sample, the performance improves considerably. For the load-balancing problem, we show that our LEARN-&- algorithm can achieve a load of
(1 + (1+ B[Opt(R)) + o log" m pE
for any > O, where m is the number of machines. Hence, if the optimal load is not too small (at least poly-logarithmic in the number of machines) then an online algorithm can achieve a load that is arbitrarily close to this optimal load. Contrast this with the worst-case setting (i.e., without a sample), where such result is provably impossible: for any online algorithm we can give instances where Opt(T) is as large as we want, and yet the algorithm's 'ss load least (log, m) Opt So having access to the random samples is provably very powerful.
For clustering (facility location) and network design (Steiner tree), we get algorithms whose cost is
Ollog 1/p) E[)]t(R))-
So when p > is a constant, say, our cost no longer depends on the size of the input. Indeed, setting := 1/1z] means we get a sample of a single element (which is conceptually like not having any sample at all), and match the worst-case bounds. In this sense, our results interpolate between the AOS framework and the worst-case.
Our Techniques. One of the main contributions of the LEARN-& -LOAD algorithm is conceptual: we show that a low-round parallel algorithm to compute a suitable parameter vector can be used to get a generalization bound. Let us explain. We Lattanzi et al. [2020] that for any load-balancing instance Rt there exists a weight vector 0 E RT such that assigning each job j fractionally machines E N(j) using the proportional allocation Jay = Eiy U(2) achieves an essentially optimal allocation. Now we could try to PAC-style
observation of Agrawal et al. [2018),
9.
arguments: compute the empirical risk minimizer using the sample S, and use it for the real requests R. Then apply uniform--onvergence bounds to show generalization. Applying this idea gives a bound of
(1 + e [R)) m poly(log m/E)
P
Notice that this result suggests we need the optimal load to be very Lurge-largen than the number of machines m-for it to exceed the second term and thereby get non-trivial results. This is unde- sirable: we want to improved results for much smaller values of Opt (like the bound of (2) we will eventually show), and PAC-style bounds on covering numbers don't seem to give such tighter bounds. (Bounds on covering numbers seem to need an exponential dependence on the dimension m, which leads to poly(m) bounds.)
A different approach would be to view the maximum load of an instance R as function of 0, and use the requests from the sample phase S to implement SGD update steps, whence the convergence guarantees of stochastic gradient descent by Nemirovski and Yudin [1983] would imply generaliza- tion bounds [Hardt et al., 2016, Hardt and Recht, 2021]. However, this approach fails because the maximum load of R (as function of 0) is neither concave nor convex.
Our approach is different: we show that (a) a multiplicative weights update algorithm to compute an optimal 0 for the instance R requires only a poly-logarithmic number of rounds (based the work

---

of Ahmadian et al. [2021D, and (b) each round can be implemented using robust load query to the instance R. The eventual idea becomes very clean: we partition the sample S into poly-logarithmic mini-samples, and use each mini-sample to implement one robust load query to R. (Here we use that S and R are both samples from I.) We hope this idea of using low-round algorithm to compute as learning algorithm might prove useful in other contexts.
The algorithm for clustering and network design follow a different conceptual message: that of using (a suitably scaled version of) the sample S to build an anticipatory solution F,, and to then augment this solution to get the solution for the real requests R.
1.1 Related Work
The AOS model was formalized by Kaplan et al. [2020, 2022]; a closely related model was given by Correa et al. [2021], who consider the items to be independently sampled with probability (instead of random pn-sized subset being chosen as the sample). Independently, Lattanzi et al. [2021] considered the semi-online setting of Kumar et al. [2019] where part of the input is given offline and the rest is online; they studied the case where a random p-fraction is presented offline. They consider the correlation clustering problem and show how the AOS model overcomes strong impossibility results. One difference between these two models is that the semi-online model seeks to bound the algorithm's ' cost on I to Opt i.e., instead of (1), it aims to show that
ER[ cost of A I| < hp)) optimal cost for I,
We focus on definition (1), but our techniques are malleable and extend to definition (3) as well.
Similar models have been studied in other contexts. In the random-order model and the secretary problem from optimal stopping theory widely used in online algorithms and algorithmic mechanism design, the input is adversarially chosen but presented to the algorithm in an uniformly random order. The major difference from the AOS model is that the second part also appears in random order. However, some algorithms (which are called order-oblivious by Azar et al. [2014]) for the random-order model do not use this randomness of R's order, and hence can be implemented in the AOS model as well. For example, the algorithm of Dynkin [1963] for the secretary problem, and the algorithms of Devanur and Hayes [2009], Agrawal et al. [2014], Molinaro and Ravi [2012] for online allocation problems; see Gupta and Singla [2020] for discussion of random-order models.
Our work falls in the broad area of ML-Augmented Algorithms (see, e.g., the survey by Mitzen- macher and Vassilvitskii [2020] or the works by Mahdian et al. [2007], Lykouris and Vassilvtiskii (2018]), where the algorithm takes some (machine-learned) advice and uses this to give an improved performance. Here we crucially address the question of how to leurn this advice from the given data. This has been done in a handful of previous works, e.g., by Devanur and Hayes [2009], Agrawal et al. [2014], Molinaro and Ravi [2012]. Lavastida et al. [2021] for order-oblivious algorithms for online allocation, but these works use PAC-style ideas which we try to go beyond. Indeed, we hope work further focuses attention on the learnability of the ML advice in these settings.
The idea of proportional allocation for load- halaneilnn and matchings was first proposed by Agrawal et al. [2018], and extended by Lattanzi et al. [2020], Li and Xian [2021]. Ahmadian et al. [2021] I] gave a distributed algorithm to compute a weight vector 0 which gives small maximum load with a small number of rounds of communication; we present an arguably simpler version of their arguments in Section 2.5, and show also works when we are just given noisy statistical access to the instance.
The online Steiner tree problem was proposed by Imase and Waxman [1991], who gave optimal algorithms and matching lower bound results. The online facility location problem was proposed by Meyerson [2001], and the upper and lower bounds were improved by Fotakis [2008]. The algorithm in Meyerson [2001] also works in the random order model, but is not order-oblivious. Garg et al. [2008] show that Steiner tree does not have any improved algorithms in the random-order model; in contrast they give competitivee algorithms when the input consists of i.i.d. samples from a known distribution; Dehghani et al. [2018] 88] claim an extension to non-identical distributions. Our algorithm for Steiner tree in the sampling model is inspired by theirs ("build a solution on the sample, and then augment").. Azar et al. [2022] give framework for network design with predictions; their ideas imply an alternative O(log 1/p) competiiteee guarantee for Steiner tree (using more involved algorithm than ours). Their approach does not seem to extend to facility location or load balancing.
3

---

2 -aalnnalnn with a Sample
In the online load-halancing problem (sometimes called the restricted assignment model with par- allel machines) the input consists of m machines which are fixed, and the online request contains n jobs arriving over time. Each job specifies subset of the m machines that be assigned to. (We consider unit-sized jobs and identical machines for simplicity, see $2.4 for extensions.) The algo- rithm must assign the job one of these machines. The load of machine is the total size of jobs assigned to it, and the goal is to minimize the maximum load over all machines.
It is convenient to think of machines being the vertices of hypergraph H, and denoting them by u, v, etc.; let V denote the set of machines, with [V] = m. Each job is a hyperedge e C V, containing the machines it be assigned to. Let E denote the set of jobs, with [F]] n. We seek an assignment : F >> V satisfying (o(e) E e for each job/edge e E F; the load of machine V is (w)]- The goal is to minimize E [mmaa, (v>]( the (expected) maximum load over all machines, where the expectation is taken over any random choices we make in finding g.
Given instance I of load- ballnbaann,nng a fractionnll assignment of these jobs is matrix X E R given by the following linear program:
PI,: =
EvEr Tew
Ve E E VVEV
Eevvee Tee L
Jee 20
}.
The smallest value of L for which this LP is feasible is the optimal fractional load FOpt(Z); if we restrict Teo to integers, then this smallest value of L is the optimal (integer) load Opt(Z). Both can be found offline using flow techniques, though our focus is in the online setting. Henceforth we use the notation load (X) := Σ. zelloo where Ie t the row of X corresponding to the job e, denoting its fractional assignment.
Our approach is to compute fractional assignment X online, and use independent randomized rounding to convert it (also online) into an integer assignment sp
Lemma 2.1. Given fractional X, randomized rounding outputs an (integer) assignment yp with
E mmax (v)]] s (1 load(X) + O(==2 lo(mm/)))
Proof. Randomized rounding sends job e to a machine independently with probability zev: the expected load of each machine pha := E. Tev, and concentration bound implies that
Pr [1p-+(w) 2 (1 + e/22 (xa + O(E log(m/e)] S
2m
Taking a union bound over all m machines increases the failure probability to at most = Finally, the maximum load is at most n and the fractional load must be at least n m, so the contribution to the expectation in the event of failure is at most is at most é
2m n < f/2 lxad(X).
Given this rounding algorithm, can focus on finding fractional assignment online with low Ioad(X) close to FZ) < Opt(Z). The randomized algorithm above can be derandomized, and also better additive losses can be obtained, see work by Li and Xian [2021]; however, these change only the lower order terms in our proofs.
2.1 The Proportional Allocation Strategy
To find fractional assignment, use an important idea by Agrawal et al. [2018], Lattanzi et al. [2020]. They show that for any instance I and any threshold À > FOpt(I), there exists a weight vector 8 E R, such that the fractional assignment
0g
Fea
Ence An
achieves (xad(x)= < A. We denote the vector of individual machine loads corresponding to this 0 and the maximum load, as
L(I : 1 = Σ xer
and
load(X) = [I, 0)
c

---

While 9 can be found using a convex program, this does not help us prove generalization bounds for the AOS model. In the rest of this section we show that (a) the natural multiplicative algorithm to compute ! converges in (log" m/e²) rounds, even with restricted and slightly noisy
access to the instance I, and then (b) how this result gives an algorithm in the AOS model.
To model the restricted/noisy access to the input I, consider the following framework: Definition 2.2 (Robust Oracle). Given any function f and a parameter k, a (k, e)-robust oracle for an instance I returns value V such that
(1 e max( VVV S (1 + (2),)
In fact, will consider such oracle only for statistical queries, where apply function f to each element the dataset Z (in our case the jobs/edges of the instance), and then return their sum, so this be viewed variant on the well-known SQ model of Kearns [1998] (see Reyzin [2020] for a survey). Note two differences with the standard SQ model: we look at multiplicative instead of additive errors, and the answers meaningful only when they are at least the parameter k.
We state the algorithms in Section 2.2 assuming robust oracle access. Our implementation these oracles succeeds with high-probability (over the random sample), hence we give high-probability cost bound Theorem 2.5.
2.2 Fractional Load Balancing Using Robust Oracle Access
In this section we show how given only robust oracle queries to an unknown instance I, we can com- pute parameter vector 0 which achieves near-optimal load for using only poly-logarihhmiaally many queries to this oracle. This will be used in the next section to get our algorithm for load- balancing in the AOS model.
Algorithm starts with an estimate 6 of the optimal weight vector (say, the all-ones vector). each round it asks for estimate of the maximum load given the current weights g--1; if the load (or rather, the estimate) for some machine is too high, the algorithm reduces the weight on that machine by factor of (1 + e)- Lattanzi al. [2020] showed that this algorithm converges, but the interesting fact of Ahmadian et al. [2021] is that it converges in few rounds of updates, and we will show how this is useful for our purposes.
Algorithm 1: Robust Algorithm to Compute Weights
Input: number of machines m, robust oracle for instance Z. initialize g + for all V
2 + estimate for optimal load FOpt(Z) from (k,e)-robuss oracle
for 1..2......7 do
x = (X/-1,....
1 +- estimate for loads L(I, 0t-1) from (ks robbsst oracle.
1.4
forall V do
a!-1 if X (1 +)² 2 then 0 <- T+E else 0 + 6-
1.6
return weight vector 1 + 0T.
1.7
Theorem 2.3 (Load Balancing using Robust Queries). For any k > 0, let y max(k, FOpt(I). In(2m/e) In
Fix E E (0, and define T : + In(++e) In(1+=/2] O log log(m/e)). ) The parameter vector returned by Algorithm ensures that the maximum fractional load is
[I, 0) s (1+ -7.
If we had direct access the instance we could use directly use the work of Ahmadian et al. [2021]. Since we access I only though robust oracles, we need a bit more care: we give the short and arguably simpler proof in Section 2.5.
2.3 The AOS Algorithm for Load-Balancee
Lemma 2.4 (Sampling Lemma). Given any instance I and (0, 1), let Ig be the sub-instance obtained by picking random fraction of jobs in I. Then
5

---

1. For k = Q?(== 1 log m). with probability 1 101-1/pool0 1/poly(m).
maxx(k,FOpt(Z.)
(1 (1+E)-'s
6Fo(k, S =).
ii. For any fixed weight vector 0. L(Is. 0) E 6(1 =) L(Z, 0) = O(E log 'lggm) with proba- bility - p/poly(m).
Lemma 2.4 implies that taking uniformly random subset of 8-fraction of the imput and using that to estimate (a) the optimal load or (b) the fractional load [, 0) for any fixed weight vector 0 gives -rrobust estimate (after rescaling by 1/5) with probability at least 1/poly(m). long as l = -Qooog m/e?).
Let T' be the number of rounds required for Algorithm 1, given by Theorem 2.3. If FOpt(Z) = O [ log taking the p-sample and breaking it randomly into T parts implies that each sample is 6-sample for := p/T. As long as the expected optimal value on each of these parts is much larger than k, our estimates are within factor (1 e) of the correct values. This means that the fractional load our assignment will also be close to FO),(I), as long as FOpt(Z) = (((T/p)
(log m/=²)) S2( log" m
pc
To summarize, the final algorithm is the following:
Algorithm 2: LEARN-&-LOL
Input: Sample S that is random p-fraction I
2.1 Randomly partition into mini-samples S1, S2,SS.,... , ST of size ISl/T
2.2 run Algorithm but use S, to estimate L(I, 1) in each round t.
Theorem 2.5. For suitably small e E 1), the
algorithun achieves any in- stance a fractional load of +O)) -FOpt + O (og((m/E) with probability 1 - p/poly(m), in the AOS model.
2.4 -aad-Baaa::iig: Extensions
The above analysis extends with almost no changes to jobs whose sizes p. lie in [0, 1]. Extending to the related machines setting requires bit more work. Here, each machine has speed s, 1, and the load of a machine is the total volume Σ. Ten assigned to it, divided by the speed. So the goal to minimize max, EE, /w)e Again, each job can only be assigned to subset of machines. Keeping the same notation, the machines form a set V of vertices, and the jobs are hyperedges denoting which machines they can be assigned to. In this case, there exist weights O Rm such that the scaled proportional allocation
8. Bev := Sq Encc On
1 (vEn)
gives a near-optimal fractional load. Moreover, for each job we can drop some of the slower machines from the allowed set to ensure that max.ce & S (m/E),
expense of increasing the
minege optimal fractional load by at most 1+s factor. Moreover, if the speeds all machines in an instance I' satisfy min, S. < M (we say such instances have aspect ratio M), then the proof of Theorem 2.5
extends to show that O log" (Mm/e) rounds updates suffice. (See supplementary material for details.) However, this is not enough, since the parameter M can be exponential in m. even allowing for + s-approximations.
g
To handle this. we can perform an instance decomposition: we show how to take any instance I and find a collection of K O(1/=) "nicer" subinstances I I!....,I* each of which has aspect ratio bounded by /m//))/=, such that each instance contains all the machines, and each job belongs all but one of these K instances. Solving each of these instances I to get assignments x² and then setting
Tee - Ee zee gives fractional assignment whose load is at most (1 + 1/(K - 1)) = (1)

---

times the maximum load of each of these subinstances, which is itself near-optimal. The number of rounds increases by approximately a factor of 1/e².
We sketch this decomposition, which is of independent interest: define the speed class of a machine be Co = In Su- Since we assumed that speeds non-negative. Assume 1/E is an integer, for simplicity, For each job e define its window We == Iminvee Cv, maXvge Co]. Now for each "shift" lo E 10. 1/e - 1), define F := {(k + 1/)- in(m/s) E 2), and define I to be set of jobs e whose window W. does not contain a value in 1*k. Note that 1* partitions the machines into groups whose speeds classes differ by at most 1/elemm lm(m/s), and keeps only jobs whose allowed machine falls within each group. (We can now re-normalize the machine speeds for each group of machines separately. so that the slowest speed in each group is 1, and now the maximum speed is most (m/e)>/E.) Finally, by our preprocessing each job has window of width at most In(m/s), so this window intersects only of the F sets, and hence the job belongs to all but one the subinstances. This completes the extension of our result the case of machines having different speeds; the guarantees suffer by only factor of 1 1/e².
least 1, the classes of all machines
2.5 Proof of Theorem 2.3
Finally, give the proof for Theorem 2.3, mostly to emphasize its simplicity. It relies on two lemmas: a quasi-monotonicily property (Lemma 2.6) and an expansion lemma (Lemma 2.7). We state these two lemmas here and prove Theorem 2.3, and defer their proofs to the appendix.
Recalling Algorithm 1, let Dt denote the number of times that machine v's weight has been de- creased by the end of iteration 6, so that 0f = (1 + +) Define x := L(I, 0'), to be the actual load on machine v when using weights 0¹, and let X be the robust estimate get in our algorithm.
We first show that if e's weight is decreased at least once then the load is not too small; and if is not decreased at least once then the load is not too large. Lemma 2.6
Let y max(k, FOpt(T).. The following guarantees hold:
(A) D', > 0, then X 2 (1 E),, and (B) if D < t, then X - (1 + 7
Lemma 2.7 (Expansion Lemma). Let
ln(2m/e), Define := {u E V D 2 8) for some In(1+s)
==
> 0, and ler = (u EV D 2 s a}. Then
;) |A].
B 2 1
2
Proof of Theorem 2.3. Consider the end of round T'; claim that each vertex has DJ T. If so, the second claim of Lemma 2.6 guarantees each vertex has load X at most (1 +)² 7. So, for contradiction, suppose there do exist vertices with D = T, i... whose 0 parameter has been reduced in each round. If we define M(s) = HE D. 2 sH}, this means M(T) Z 1. Now applying Lemma 2.7 repeatedly,
M(T - jo) Z (1 (1+ M(T) (1+
Hence, 7f > a log( +3/3 we have M(1) > m, which gives contradiction. This means there are no vertices with DJ = T, which completes the proof.
log
3 Clustering and Network Design in the AOS Model
The online Steiner tree and facility location problems both fundamental questions in discrete optimization, for which can use the sampling in the AOS model to give an improved performance of Ollo 1/p), whereas the worst-case performance must depend on the size of the instance. For the rest of this section, we assume that p Σ 1/2, so that the sample is a small part of the entire instance.
Both these problems are subadditive covering problems: any superset of solution is another so- lution; moreover, given any two instances Σ,, I2, the union of their solutions is also a solution to the union of their instances. This implies that (Tt UI2 < Opt(Z,) + Opt(Zz). Now for instance I, if is a p-sample for p S 1/2, and R the remaining requests, this fact implies that E[Opt(R)] 2 1/2- Opt(I).
7

---

3.1 Online Steiner Trees
Let (V,d) be finite metric space with a fixed root node r, where the points V1, U....... . Un of V are revealed one-by-one. At time t we find out the distances from Us to the preceding points v (for < t), and must connect it to one of them. (Think of 2g =r.) The goal is build minimum-length spanning tree for (wo, .i,.... J. free problem; the optimal competitive ratio for this problem is (log n) due to Imase and Waxman [1991]. In the AOS model, the set V is randomly partitioned into the sample S and the "real" points R, where |S| = pn. We then see the sample up-front, followed by the points R in some adversarial order. The goal is to build a minimum-length tree that contains all the points in Rt; it can also contain any subset of S. The proposed algorithm is simply an augmented greedy algorithm:
This problem is often called the online Steiner
Build a minimum-lenghe spanning tree T connecting the sample S. Now if the points in R are denoted ri, "", then connect rt to the closest point in S U
In other words, after we buy an MST on the sample, we simply run the greedy algorithm. (This algorithm is directly inspired by that of Garg et al. [2008] for the case of i.ddd samples from a known distribution.)
Lemma 3.1. For S 2/2, we have [[Alg(R)) s O(log 1/D) Opt(V)= S Olog 1/2) E[(Opt (R)).
Proof. The cost of the MST on the sample Opt(S) S OVL((V. so it suffices to bound the aug- mentation cost for requests in R. Consider the minimum-length spanning tree T for V; taking an Fulerian tour and shortcutting repeated vertices gives cycle C" of length at most Opt(V) con- necting all points in V. The sample S breaks this cycle into paths; for each edge E C*, let Le be the number of vertices on this path containing e, and let de denote its length.
Claim 3.2.
B[Alg(RR)] S so [[Alg(R)){
E
{
dd de log Le
Σ
s so
Σ de log E(Lee)
Proof. The proof is very similar to showing that the greedy algorithm is O(log comppttite on sequences of length k; we give it here for completeness. Let P be one path in the partition of C*,, where P = (s uo. U1, U2, Ua-1, = s') with s = uo and u, = s' belonging to S, and all other u, E S. Let = (ug. ..., ]. Taking alternate edges partitions P into two matchings, each of length at most EcEp de. Consider the matching M with at least half the edges in P: for each edge e == =((u; Uj) E .M, the cost of connecting the later-arriving of the two (say u,) greedily is at most d(u,, uy) S de- Hence the total cost for connecting all these later-arriving vertices is at most Eeep de. This accounts for half the vertices on P; now dropping all these later-arriving vertices from A, and repeating the argument log, times shows that the total cost incurred for nodes in P is at most Ologg IP]) Eeer de. Finally, summing over all the paths completes the proof of the first inequality. Then using Jensen's 's inequality along with the concavity of the logarithm function gives the second inequality of the claim.
Finally, S is random subset of pn points from V (giving a hypergeometric distribution), so the number of hops from the edge to the closest vertex in each direction in S is bounded above by geometric random variable with parameter p. which has expectation 1/p. This means E[[..] S 2/p. and now Claim 3.2 and the fact that E(Opt( 2 (V)pt(V) for p S 1/2 completes the proof. L
3.2 Facility Location
In the facility location problem, again a metric space (V,d) is revealed online; we maintain a set F C V of opened facilities at each time, and for each revealed vertex vy. we can (a) add uy to the set of opened facilities at cost f, or (b) assign vj to a previously opened facility E F at cost d(o,, i). The objective is to minimize the sum of the facility costs and the assignment costs, namely
[FI. Σ d(j,F)
JEV
Here d(f.F) = min(d((j)) lie F}.
8

---

Our AOS algorithm is the following: given a random sample S S V with pn clients, let the real set := V.S S be the remaining (1 p)n clients. In the first stage, imagine each client in S to have demand 1/p; use a constant-factu approximation to the facility location problem to find F minimizing
+I-S+ d(j,F). (L/p). JES
Now in the second stage, run Meyerson's 's algorithm on the remaining clients. Specifically, define F F; now for each client j E R. let 6g be the distance d(j, F). Open facility at with probability min(1, 6 f) (and therefore add j to F), else pay at most 6, to connect to this facility. Note that the expected cost for each j E R is at most min(1,63/ f) f (1 min(1, (z ô5 S 2 min(f, 5z).
Lemma 3.3. For p S 1/2, we have E[Alg( [R) S Ollog l/D) OV)(V) S Olog 1/n) BB(Opt (R))-
Proof. Consider the cost of the optimal solution F* for the first stage: the expected cost is at most e S) (1/p) Opt(V).
|F f
Σ
jEV
Hence the constant-factor approximate solution F incurs cost of at most O(Opt(V)) in the first stage. It now suffices to bound the cost incurred in the second stage, i.e., on the clients in R.
Consider the optimal solution for V. and let i" be open facility which serves some subset ("clus- ter") of clients; by renumbering, let these clients be C-- == (1, 21...... mm S V order of increasing distance from i". Let the total connection cost of these clients be Z,- = Σj= d(j, i*). Some of
these clients j1 < j2 .... < jı belong to the sample S; let the facility in F serving client ja be denoted i. E F. First, for a client j E (JasJa+1),
(4) since ja j and hence its distance to 8 is no larger. By our observation above, the expected cost incurred by such j is at most 2 min( f) S 26.. Summing over such clients, all indices a 2 1, and over all optimal facilities i", the first term the right of (4) sums at most twice the optimal connection cost; and the summation for the second term has each ja appear at most 1/p times in expectation, so its expected value is at most the connection cost of the first-stage solution, and hence at most ((Opt(V)). Hence the expected connection cost for these clients j 2 ji is ((Opt(V) (V)); it remains bound the connection cost of "close" clients C₁ {1, 21..2..... /1 - 1}. We claim that this cost is at most O Olog (1) Ze- now using the fact that Elji] = O(1/p) and Jensen's 's inequality on the
6, = --d F) S d(j, P)= S d(j,i") + d(i", ia) d(ja;ia) S 2dd(ji") + d(ja, in),
logarithm function, the expected cost is at most Olog 1/p) Z,- for this cluster, which completes the proof.
The proof of the Ologgín) Zz- bound mimics that given by Meyerson [2001]: let be the average cost of these "close" clients in the subset C.,. We group these clients j into annulii based on their 5, values being in the intervals [0, 2]. (z, 22]..... (22 2, 2 2).,..... we can restrict the exponent k to at most log2 J1, else the connection cost of that single facility would be too high. Let G be the subset of clients in some interval (2 2, 2* z]: the expected cost incurred until the first facility is opened (say at location j') in this subset is most 2 after which the expected costs are at most O(d(j.J') < O(d(j, i)). The sum over the clients in G is at most the cost of this cluster in expectation. Hence each annulus costs at most (Z ); there are log, j1 annulii, which proves the Ologgji) Zz- bound.
using a primal-dual algorithm was given by Fotakis [2008]; we leave it as an open problem to extend our result to give an O
A better competitive ratio of O log r
log log
log 1/2 log log 1/p algorithm.
4 Conclusions
There are several directions for future work. The current bounds for load- balancing are not tight: our techniques cannot be directly improved, but we hope that future work can improve the bounds on the additive load. While we can extend our results to related machines (where the size of job on machine i is 1/8, for some "speed"" 8;), we not know how to extend our results (and specifically the expansion lemma) to unrelated machines where each job j has a size Pij E [0, 1] for machine i.

---

Acknowledgments
This research was supported in part by NSF awards CCF-1955785, CCF-2006953, CCF-2224718, and DMS-1952285. We thank Marco Molinaro for many useful discussions.
References
Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. dynamic near-optimal algorithm for online linear pro- gramming. Operations Research, -940 2014. doi: 10.128770pre.2014.2222 URL http: //dx. org. 10. 1287/ /oree. 2014. 1289. (Cited on 3)
Shipra Agrawal, Morteza Zadinoghaddam, and Vahab S. Mirrokni. Proportional allocation: Simple, dis- tributed, and diverse matching with high entropy. Jennifer G. Dy and Andreas Krause, editors, Proceed- ings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmåssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 99-108. PMLR, 2018. URL http: / /ttp///eeeeeens..//ee/ mlr vrees/vv0// agraa agrawal18b. html. (Cited on 2, 2,
Sara Ahmadian, Allen Liu, Binghui Peng, and Morteza Zadimoghaddam. Distributed load balancing: A new framework and improved guarantees. James R. Lee, editor, 12th Innovations Theoretical Computer Science Conference, ITCS Jamuary 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 79:1- 79:20. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021. doi: 10.4 10442000PPtss.7TSS2201.... URL https://dol org/ 10. 4230/LIPIcs. ITCS, 2021 79. (Cited on 3)
Pablo D. Azar, Robert Kleinberg, and S. Matthew Weinberg. Prophet inequalities with limited information. In SODA. ACM, New York, 2014. (Cited on 3)
Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM- SIAM Symposium on Dis- crete Algorithms, SODA 2022, Virtual Conference /Alexandria, VA, USA. January 9- 12, 2022, pages 35-66. 1137/1 SIAM, 2022. doi: 10. 10.1133/1..9888 17716119777177333 URL htttttttp///i.ooo 1110001111177119771111777777 9781611977773. (Cited on 3)
3.
José R. Corea,, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, and Alexandros Tsigonias-Dimitriatt Dimmitiadis.. The secretary problem with independent sampling. In Dániel Marx, editor, Proceedings of the 202/ ACM- SIAM Symposium Discrete Algorithms,, SODA 2021, Virtual Conference, January 10 13, 2021, pages 2047-2058. SIAM, 2021. doi: 00.111771.97711111966651. 9781611976465, 122. (Cited on 3)
URL https://doi org/10 1137/1.
Sina Dehghani, Sohcil Ehsami, MohammadTaghii Hajiaghayi, Vahid Liaghat, and Saced Seddighin. Greedy algorithms for online survivable network design. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium Automata, Languages, and Program- ming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPles, pages 152:1-152:14. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/L.PIss.CALPPPP https: //doii org/10. 10. 4230/LIPIcs. ICALP 2018. 152. (Cited on 3)
URL
Nikhil R. Devanur and Thomas P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In John Chuang, Lance Fortnow, and Pearl Pu, editors, ACM Conference on Electronic Commerce, pages 71-78. ACM, 2009. ISBN 278-1-6005884588- (Cited on 3)
E. B. Dynkin. The optimum choice of the instant for stopping Markov process. Soviet Math. Dokl, 4, 1963. (Cited on 3)
Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1577 2008 doi: 10.11077/00455-0077 9079999999 URL huttps:///ee
(Cited on 3, 9)
Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online combi- natorial optimization problems. In SODA, pages 942-951, 2008 doi: http://doi..cm..rr///// 10.1 145/1 347082. 1347185. (Cited on 3,
Anupam Gupta and Sahil Singla. Random-order models. In Tim Roughgarden, editor, Beyond the Worst- Case Analysis of Algorihmms, pages 234-258. Cambridge University Press, Oct 2020. doi: 10.1017/ 9781108637435.055 URL https: wttg//.00117//78110883333333
015. (Cited on 3)
Moritz Hardt and Benjamin Recht. Patterns, predictions, and actions: A story about machine learning. CoRR, abs/2102.05242,, 2021. URL httpp:://aaai abspg//abb//////// 05242............2222222222222 (Cited 2)
10

---

Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradi- descent. In Maria-Florina Balcan and Kilian Q Weinberger, editors, Proceedings of the 33nd In- termational Conference on Machine Learning, ICML 2016, New York City, NY. USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1225-1234, JMLR.org, 2016. URL http:/ http://proceedings mlr. boess//48/hartt.t htmml.
html. (Cited on 2)
Makoto Imase and Beraard M. Waxman. Dynamic steiner tree problem. SIAM J. Discret. Math. 4(3):369-384, 1991. doi: 10.1137/0404033, URL httpss://oi org/ 0rg/10.111 1ww.111137444000 (Cited on 3, 8)
Haim Kaplan, David Naori, and Danny Raz. Competitive analysis with sample and the secretary prob- lem. In Shuchi Chawla, editor, Proceedings of the 2020 ACM- Symposium on Discrete Algo- rithms, SODA 2020. Salt Lake City, UT. USA, January 5-8, 2020, pages 2082 2095. SIAM, 2020. doi: 09.11371.78861119779999 1,
URL https://ddol httpp::/ddoi.org//10 10/g/10..111 0tt.:/11177111119778898 128. (Cited on
Haim Kaplan, David Naori, and Danny Raz. Online weighted matching with a sample. In Joseph (Sefti) Naor and Niv Buchbinder, editors, Proceedings the 2022 ACM-SIAM Symposiun on Discrete Algorithums, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9- 12, 2022, pages 1247-1272. SIAM, 2022. doi: 10.1137/1 0111137/19781161117777335 URL https: //doi///ooooo http://..............././.111110 07111119711111111177111 3)
(Cited on
Michael Kearns. Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6):983-1066, 1998. doi: 10.1 00.1145293347:2993351 URL
org/10. 1145/293347 29213444779935.11 293351. (Cited on 5)
Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-online bipartite matching. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIes, pages 50:1-50:20. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019. doi: 10.42:00 201..... 4230/LIPIcs LTCS. 2019.50. (Cited on 3,
URL BRK.httpp://Boo.or///
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via Icarned weights. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1859-1877, 1877. SIAM, 2020. doi: 10.1 137/11 978161 1975994. 114. URL https: : //doi. org/10. 1137/ /1. 9781119979999 114. (Cited on 2, 3, 5)
Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang. and Rudy Zhou. Robust online correlation clustering. In Marc'Aurella Ranzato, Alina Beygelzimer, Yanu N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: An- nual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 4688 (688-4698, 2021. URL pettss//prroeedingg Abstract. html. (Cited on 1)
Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance-robus. predictions for online matching. flows and load balancing. In Petra Mutzel, Rasmus Pagh. and Grzegorz Herman, editors. 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of L.Plcs, pages 59: 59:1-594 1-5:177. Schloss Dagstuhl Leiiniz--enntmmm für Informatik, 2021. doi: 11230//IPIcc..SA..200 .59, URL https://doo org/10 10. 4230/LIPIca....... ESA. 2021. 59. (Cited 3)
Shi Li and Jiyy Xian. Online unrelated machine load balancing with predictions revisited. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 6523 6532. PMLR, 2021. URL
mlr www.:rreesssvveee /1w9////wwww./... html. (Cited on 3, 4)
Thodoris Lykouris and Sergei Vassilvtiskii. Competitive eaching with machine learned advice. In International Conference on Machine Learning, pages 3296-3305. PMLR, 2018. (Cited on 3)
Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online advertisement space with unre- liable estimates. In Jeffrey K. MacKie Mason, David C. Parkes, and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007, pages 288 294, ACM, 2007. doi: 10.1145/1250910.1 1250952. URL httpp:://oi.orggeeeeee 114501250900 1250952. (Cited on 3)
Adam Meyerson. Online facility location. 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 426 431. IEEE Computer Society, 2001. doi: 10.1109/SCSS200 2001 959917. URL https: //doi.. org/ 10. 1109//FCS 2001. 959917. (Cited on 3.
9)

---

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden, editor, Beyond the Worst-Cuse Analysix of Algorithms, pages 646-662. Cambridge University Press, 2020. doi: 7L.10179978110867433..333 URL http://///....aooooo.o./////1111
037. (Cited 3)
Marco Molinaro and R. Ravi. Geometry of online packing linear programs. In Automata, languages, and programming. Part volume 7391 Lecture Notes Comput. Sei., pages 701-713. Springer. Heidelberg. 2012. URL http:// / dz. doi. org/10 10. 1007/978 1/////977883988 1-78--3-6----- 0--644--11855 3----3119------ -_9. (Cited 3)
Arkadi Seměnovich Nemirovski and David Berkovich Yudin. Problem Complexity and Method Efficiency
Optimization. John Wiley Sons, Inc., 1983. (Cited on 2)
Lev Reyzin. Statistical queries and statistical algorithms: Foundations and applications. abs/2004.00557, 2020. URL hattp:///araae http:p////aaiiooo/aaaa////////// 00557. (Cited on 5)
CoRR,
Tim Roughgarden, editor. Beyond Worst- Cast- Analysis of Algorithmms. Cambridge University Press,
2020. ISBN 9781 108633733.
doi: 1111017/9781108377700 URL https://doi. org/10.1017/
9781108637435. (Cited on I)
12


Reviews:
[{"review_id": "Me3O4sQdwQ", "reviewer": "Reviewer_qRGt", "summary": "The paper looks at the problem of learning in an online setting where instead of seeing all points one by one, they give a sample of the points and then use it as an initial set to achieve better bounds for the problems, the restricted assignment load-balancing problem, the Steiner tree network design problem, and facility location clustering. Assuming a p fraction of the points is observed as a sample, they bound the competitive ratio using a function of p. They provide an algorithm, Learn-&-Load for load balancing which gives a $1+\\epsilon$ ratio (plus an additive factor that depends on the logarithm of the number of machines). They also provide algorithms for Steiner tree network design problem and facility location clustering that has a ratio of $O(\\log 1/p)$.", "questions": "How does this compare to the models where you have some hints or predictions on how the data points would be rather than sampling upfront? Just curious.", "limitations": "The paper states the limitations of the methods they have proposed and the non-optimality of the bounds they have provided for the load-balancing problem. They note that the current method they have suggested cannot be directly improved and leave the discovery of the improved bounds as an open problem. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality: The idea of using sampling to pre-learn information and improve competitive ratios is an idea they are borrowing from a earlier work as they have stated. Similar ideas have also been used in some online clustering algorithms as well. The work of the paper is to mainly introduce the algorithms that perform well.  They basically use the idea to solve 3 online learning problems. \n\n- Quality and Clarity: The paper is well written and clearly formatted. It is easy to follow the flow.\n\n- Significance:  This extends the use of the sampling model to cover three interesting problems. However, it is not entirely clear how significant it is to find improved algorithms for this specific set of problems.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M1TtnF7FlTQ", "reviewer": "Reviewer_sgBf", "summary": "The paper develops \"Online Algorithms with a Sample\" for the problems of online makespan minimisation on related machines, online facility location and online Steiner tree. \n\nOnline Algorithms with a Sample is a relatively new model that assumes that the an arbitrary instance I is chosen by the adversary and the Algorithm receives a random p-fraction of the instance before having to process the instance in an online fashion. The main idea behind the model is that the p-fraction naturally serves as a training set for the algorithm. The paper provides algorithms within this model that essentially have a performance guarantee independent of the size of the input (which is possible in the classic worst-case online model). The exact bounds can be found on lines 49 and 56 of the paper. The (not so surprising) caveat is that the performance now depends on p -- the size of the fraction of the input that the algorithm has access to. Depending on the particular problem and input this can be quite powerful (for example in the unrelated machines scheduling problem if the optimal makespan is much higher than the number of available machines).", "questions": "Am I right about the implicit assumption regarding the upper bound on the job sizes, or am I missing something?", "limitations": "Yes, they have.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nI really enjoyed reading the paper, it considers a relatively new but very natural model and proves very interesting results. The highlight, is probably the result on the scheduling problem, which combines known observations with a very simple multiplicative weights update algorithm to derive the obtained result. The latter two results are also quite elegant, although perhaps a tad too simple for justifying acceptance on their own.\n\nWeaknesses:\n\nI could only identify minor weaknesses in the paper. First, it seems that there is an implicit assumption on a known upper bound on the job size with respect to the scheduling problem. This should be discussed further. It would be nice to also have a discussion about where the difficulty lies in extending/adapting the results for the unrelated machines setting. Finally, I think the model lends itself very well to experiments and I would be interested to see to what extent the suggested model outperforms classical algorithms.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4WNSj7sSqB", "reviewer": "Reviewer_SzP5", "summary": "The paper discusses three problems in the context of online computing with a sample. In this context the online algorithm is presented with a random sample of a $p$-fraction of the input sequence, and then as to serve the rest in adversarial order. The three problems are load balancing (of restricted jobs), facility location, and Steiner tree. In all three cases, the worst case competitive ratio is logarithmic in input sequence length, for fully adversarial sequences. This paper shows substantial improvement for, say, constant $p$. In the case of load balancing, the improvement is mostly if the optimum is not too small. In the other two problems, the improvement is more impressive: it's logarithmic in $1/p$. The methods used in the algorithm for the load balancing case (proportional response and multiplicative weights) are also substantially different from the methods used for the other two problems (augmenting a good solution for the sample, using a standard algorithm for the worst case).", "questions": "None.", "limitations": "Irrelevant.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a very nice paper that gives strong results (mostly for facility location and Steiner tree) in a recently explored model of beyond worst case online computing. The algorithms are simple and natural.\n\nThe main weakness is that there are no matching lower bounds. In fact, the authors themselves point out that there is a better worst case result for facility location that has the potential to be used to improve slightly their beyond worst case upper bound.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept