Discrete-Smoothness in Online Algorithms with Predictions
Authors: Yossi Azar
Debmalya Panigrahi
Noam Touitou
Venue: NeurIPS 2023 poster (2023)
Keywords: Online
Predictions
Learning-augmented
Facility Location
Set Cover
TL;DR: We introduce a new notion called discrete-smoothness in online algorithms with predictions that smoothly interpolates between the established desiderata of consistency and robustness.

Abstract: In recent years, there has been an increasing focus on designing online algorithms with (machine-learned) predictions. The ideal learning-augmented algorithm is comparable to the optimum when given perfect predictions (consistency), to the best online approximation for arbitrary predictions (robustness), and should interpolate between these extremes as a smooth function of the prediction error. In this paper, we quantify these guarantees in terms of a general property that we call discrete-smoothness, and achieve discrete-smooth algorithms for online covering, specifically the facility location and set cover problems. For set cover, our work improves the results of Bamas, Maggiori, and Svensson (2020) by augmenting consistency and robustness with smoothness guarantees. For facility location, our work improves on prior work by Almanza et al. (2021) by generalizing to nonuniform costs and also providing smoothness guarantees by augmenting consistency and robustness.

Discrete-mmoothness in Online Algorithms with Predictions
Yossi Azar Tel Aviv University azar@tau.ac.
Debmalya Panigrahi Duke University debmalya@cs. duke. edu
Noam Touitou" Amazon noamtwx@gmail. com
Abstract
In recent years, there has been an increasing focus on designing online algorithms with (machine-lcarned) predictions. The ideal -arninng--ugmeneedd algorithm is comparable to the optimum when given perfect predictions (consistency), to the best online approximation for arbitrary predictions (robustness), and should interpolate between these extremes smooth function of the prediction error. In this paper, we quantify these guarantees in terms a general property that we call discrete- smoothness and achieve discrete-smoode algorithms for online covering, specifically the facility location and set cover problems. For set cover, our work improves the results of Bamas, Maggiori, and Svensson (2020) by augmenting consistency and robustness with smoothness guarantees. For facility location, our work improves prior work by Almanza al. (2021) by generalizing nonuniform costs and also providing smoothness guarantees by augmenting consistency and robustness.
1 Introduction
The field of caanninn--ugmmnntee online algorithms has gained rapid prominence in recent years. The basic premise is to provide online algorithm with additional (machine-learned) predictions about the future to help bypass worst-case lower bounds. Since machine-learned predictions can be noisy in general, key desideratum of the model is that the competitive ratio of the online algorithm should degrade gracefully with prediction error. In particular, the cost the algorithm should be bounded against that of the predicted solution (called consistency) that of an online algorithm without predictions (called robustness) and should smoothly interpolate between the two with increase in prediction error (called smoothness). (The terms consistency and robustness were originally coined by Purohit, Svitkina, and Kumar 388 While robustness and consistency are notions, smoothness depends prediction error which has been defined in a problem-specifi manner. In this paper, we introduce a novel, smoothness called discrete-smootfnees that applies to any combinatorial problem. As illustrative applications of this new framework, we design discrete-smooth (learing-auugmenta) algorithms for two classic problems, facilit location and cover, which improve and generalize previous results for these problems due to Almanza et al. (NeurIPS '21 (1) and Bamas et al. (NeurIPS '20 [II..
notion of
First, introduce bascrete-smoothness Suppose are given problem instance of size Let OPT be a solution for this instance. (The reader may think of OPT as an optimal solution, although our guarantees will hold for any feasible solution.) Let the predicted solution be S. Ideally, S OPT; therefore, in general, OPT comprises two parts: the predicted part OPT|s := OPT unpredicted part OPT OPT S. On the predicted part OPT]s, the algorithm has meaningful signal from the prediction but the noise in the signal is given by the overprediction &a == IS! OPT]. Naturally, the competitive ratio of the algorithm this part will degrade with increase in this noise. On the unpredicted part OPT 5. the algorithm does not have any signal from the prediction and
and the
"This paper does not relate to the author's work at Amazon.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

cannot hope for better competitive ratio than that of an online algorithm without prediction. Slightly abusing notation, we use OPT]s. ( denote both the aforementioned sets of items and their total cost; putting the two together, a learning-angmented algorithm ALG should satisfy
ALG O(f(s>)) OPT]s + O(f(n)) OPT|5
(I)
where O(f()) is the competitive ratio without prediction. We call the property of Equation discrete- smorteessmootnness.
Let us first argue that Equation recovers consistency and robustness. Consistency follows from setting S = OPT; then, Equation ( demands a constant approximation to OPT. Similarly, robustness follows from the fact that for any S, the right hand side of Equation ① is most O(f(n)) OPT.
Next, we show that the two terms ((sA) and f(n) Equation ① are the best possible. For the first term, consider prediction S comprising the entire instance (of size n); in this case, we cannot hope for the better than f(n) competiitve algorithm: thus, f(s)) is necessary in the first term. And, for the second term, consider empty prediction S O, in which case again cannot hope for better than f(n) -copetiitive algorithm: thus, f(n) is necessary in the second term. Note that the asymmetry between these two terms necessary: specifically, f(1) cannot be replaced by f(OOPT) S)) since that would imply an f ((OPT) compettcoeeeiiive online algorithm when S = 0. This is impossible, e.g., for the set cover problem.
technical subtlety of the definition of discrete-smoothness (Equation (T) is that given a fixed prediction S, the minimum value of the right hand side might actually be a solution OPT that is different from an optimal solution to the problem instance. So, although the solution OPT is intuitively an optimal solution, we require that discrete-smoode algorithm satisfy Equation ( for all feasible solutions OPT, and not just optimal solutions.
1.1 Our Results
We apply discrete-smoothhesss to the classic problems of online facility location and set cover. For these problems, we obtain results that improve on prior work. We describe these next.
Online Facility Location with Predictions. In the online facility location problem, we are given offline metric space (X, 6) of m := |X] points, where each point v X has associated facility opening cost O, 2 O. On receiving an online request for a client at some location x E X, the online algorithm must connect the client an open facility at some location v E X incurring connection cost (x, v). At any time, the algorithm is also allowed to open a facility at any location E X by incurring the opening cost oy. (Note that a client cannot update her connection even if a closer facility is opened later.) The total cost of the algorithm is the sum of opening costs of opened facilities and connection costs of clients.
The first result for the online facility location problem is due to Meyerson randomized algorithm with competitive ratio of O n) for requests. This result was first
33 who obtained a
derandomized [18, and later the competitive ratio slightly improved to O logn
19 by Fotakis.
Inglog
This latter bound is asymptotically tight. More recently, the online facility location problem has been considered in the context of machine-learne' predictions (OFLP) by several papers [20 22) Of these, the work of Almanza et al. [T] is the closest to our work (the other papers use metric error measures that are incomparable to our results). In M. the offline input additionally contains predicted solution of facilities 5 ç X, where we denote |S| = s. By restricting the available facilities to the predicted set, they obtained an (log compptiite algorithm for uniform facility opening costs, under the condition that OPT C S.
We improve and generalize the Almanza et al. work by giving a discrete-smooth algorithm for the OFLP problem, i.e., an algorithm ALG that satisfies Equation (I):
Theorem 1.1. There is algorithm ALG for online (nonuiiform)aacii location with a predicted solution that satisfies for every solution OPT
ALG S Olog 8A) OPT|s + O(log n). OPT]s
(2)
where is the number of facilities in S OPT and is the number of online requests. Here, OPT (resp., OPT represents the sum of opening costs of facilities in OPT n S (resp., OPT \ S) and connection costs of all clients connecting facilities in OPT n S (resp., OPT S).
2

---

This generalizes and improves the Almanza et al. result in three ways:
The result generalized from uniform facility opening costs to arbitrary (nonuniform) costs. In fact, even for the online facility location problem (without prediction), we get an Oloo m) -competitive algorithm for arbitrary (nonuniform) facility opening costs previously, Almanza al. only established this for uniform costs.
The assumption that OPT ç S, i..., the prediction contains the entire solution, is no longer required.
If OPT _ S (i.e., under the assumption of the Almanza al. result), the competitive ratio improves from (log s) to O(logss) That is, the dependence is only on the prediction error and not the entire prediction.
In some situations, the length of the request sequence can exceed the size of the metric space m. To address this situation, we show that can be replaced by m the above result:
Theorem 1.2. There is an algoritim ALG for online (nomuniform) facilty location with a predicted solution S that satisfies for every solution OPT
ALG S Olog SA) OPT Ologgm) OPT
(3)
where m the number of facilities in the metric space overall.
Online Set Cover with Predictions. In the online set cover problem, we are given offline universe of elements and m sets defined on them U c 2 with nonnegative costs. each online step, we get new element e E E. If is not already covered by the current solution, then the algorithm must add new set from U that contains e to its solution. The total cost the algorithm is the sum of costs of all sets in its solution.
Alon et al. (3] gave the first algorithm for the online set cover problem by introducing the online primal dual method, and obtained a competitive ratio of O(log m log n) where n denotes the number
of requests. They also proved an almost matching lower bound of Tog log megng log
Bamas, Maggiori, and Svensson [1]] extended their work to online cover with predictions (OSCP), where the offline input additionally contains a predicted solution of sets S S U. They established consistency and robustness bounds for this problem by adapting the online primal dual method to use the predicted solution. The cost of their algorithm is bounded by the minimum of ( n) times the cost of the prediction and (log m log n) times the optimal cost. However, one cannot achieve smoothness through their work without choosing a trust parameter correctly in advance of the input.
log log n
We obtain discrete-smont smooth algorithm for the OSCP problem, thereby giving the first algorithm for OSCP that goes beyond only consistency and robustness and achieves a smoothness guarantee:
Theorem 1.3. There an algorithm ALG for online set cover with predicted solution that satisfies for every solution OPT
ALG S O(log SA logn) OPT mlg OPT
(4)
where SA is the number of sets in SYOPT. Here, OPT (resp., OPT represents the sum of costs of sets in OPT n S (resp., OPT S).
1.2 Our Techniques: A Framework for Discrete-Smooth Algorithms
At a high level, our framework merges two online algorithms to obtain a discrete-smooth algorithm. The algorithms differ in the guarantees they provide. The first algorithm ALG, gets a sharper competitive ratio of (s)) but against the optimal solution restricted to the prediction S. The second algorithm ALG₂ has the standard competitive ratio of (f)( but against the unconstrained optimum OPT. The main challenge in the combiner algorithm (call ALG) is to decide how to route online requests to the two algorithms. The natural choice would be decide this based whether OPT or OPT serves the request in OPT: in the first case, the request should be routed to ALG, and in the second case, it should be routed ALGz, But, of course, we do know OPT and therefore don't 't know OPT|s and OPT
Before describe the combiner strategy, consider the properties that these algorithms need to satisfy.
3

---

First, consider the subset of requests served by OPTIs. Intuitively, ALG; should be compet- itive on these requests, which means that we need stronger property from ALG, that its cost any subset of requests is competitive against the optimal solution for this subset. We call this property subset competiriveness |ymmetticclly,, subset competitiveness of ALG ensures that it is competitive on the requests in O
Next, we need a guarantee on the cost of ALG] on OpTly. and symmetrically, of ALG₂ on OPTIs. For this, we first augment ALG ALG₂ to address the prize-collecting version of the original problem, where each online request can be ignored at a penalty cost. (Note that this is more general than the original problem where every online request must be served, since the latter can be recovered by setting the penalties to be infinitely large.) Setting the penalties appropriately, we ensure that the total penalty of the requests in OPT|s bounded against the cost of ALG, on those requests (similarly for O
Finally, we require that the cost of ALG ALG₂ on any set of requests is bounded against the total penalty of the requests. We call this strengthened competitiveness w.r.t. penalties the Lagrangian property [1 Note that this ensures that the cost of ALG,, ALGz on OPT OPT are respectively bounded.
Now, we give the formal definition of Lagrangian subset-competitivenne that we motivated above. We use ALG(Q' (")))")) refer to the total cost of ALG incurred when addressing subset Q' S Q as part of running on an input Q. For any prize collecting solution SOL for input Q, we separate its total cost into SOL à (Q) (buying cost) and SOL' (Q) (penalty cost). We formalize the Lagrangian subset-competitiveess property below:
Definition 1.4 (Lagrangian subset-competitiv algorithm). Let ALG be randomized prize- collecting algorithm running on an input Q. For any competitive ratio B. we say that ALG is Lagrangian B compseetcommeettive if for every subset Q' Q we have
B[ALG(Q')@) s B OPT 0(1) OPT"(Q)
If in the equation above we replace the unconstrained optimum (OPT) by the optimal solution that can only use the prediction S, we say that ALG is Lagrangian B-subset-competttiv w.r.t. S.
We now give the combiner algorithm:
Algorithm 1: Smooth merging framework (The combiner algorithm)
be two prize-collecting Lagrangian subset-competitive algorithms. 2 Event Function UPONREQUEST(Q)
Let
3 Let a be the minimum penalty such that releasing (q.a) to ALG,, ALG2 would result in the request being served in either ALG] or ALGz. (The value of a can be determined by standard "guess-and-double")
Release (g.a) both AL.G and ALG2. Buy the items bought by AL.G], AL.G2 as result of this step.
The algorithm is simple: for a new online request q, the framework chooses the minimum penalty which ensures that least one of the two constituent algorithms ALG,, ALG2 would actually serve q (instead of paying the penalty). (q. a)) is then presented as a (prize-collecting) request to both algorithms. (Recall that the combined algorithm is for the non-priza non-prize-colle prize-collecting problem, but the individual algorithms ALG,, ALG, are for the prize-collecting problem.) At this stage, one of the algorithms serves the request (due to the choice of Q) while the other may choose to pay the penalty. The combiner algorithm now simply buys all items bought by either algorithm.
Finally, we state the guarantees of the combiner algorithm informally. (For formal deseription, Appendix (
Theorem 1.5. (Informal) If ALG,, ALG, are Lagrangian B-subset- algorithms for B f(s), respectively, then Algorithm satisfies the discrete-smootthnss property (Equation
2Our subset-coopptttiivenss property is similar (
3 OOur Lagrangian competitiveness is similar to the Lagrangian multiplier preserving property in approximation algorithms for prize-collee collectnn problems, e.g.. 37 26)

---

Applications of Theorem 1.5 Section and Appendix B give Lagrangian cubse--comeetttive
algorithms for facility location, and Section gives Lag cover. Given these constituent algorithms, we use Theorem 1.5 to prove Theorem I.T Theorem 1.2
competitvee algorithm for set
for facility location and Theorem 1.3 for set cover. These proofs are given in Appendix
Related Work. There is growing body of work in online algorithms with predictions in the last few years (see, e.g., the surveys [35 36)). This model was introduced by Lykouris and Vassilvitskii for the caching problem [32] and has since been studied for variety of problem classes: rent or
buy 25
5 39.. covering [TT], scheduling [7
10
28 34 30 8), caching [31 40) 24]
13. matching 29
16
graph problems 6 22
4
20
9
and so on. Prior works online
facility location with predictions either do not consider prediction error 1 or use continuous notions of error [2 20] such functions of the distances between predicted and optimal facilities. Our discrete notion of error refers only to whether an optimal item is predicted. Similarly, prior work on online set cover with predictions [1] 4] also does not consider prediction error. Finally, we note that discrete prediction error (similar to this paper) as well as hybrids between discrete and continuous error have also been considered 42 9 [4] but the prediction here is on the input rather than the
solution.
2 The Framework
We now describe some of the concepts of the framework in more detail.
Reduction from 8& to s. Recall that we seek snacrete-smoote algorithms, i.e., satisfying Equation ( Our first step is to give generic reduction that allows us to slightly weaken the guarantee to the following:
ALG S O(f(s)) OPTIs + (f)())) OPT/S
(6)
where O(f(-)) is the competitive ratio without predictions. We give a reduction from an algorithm that satisfies Equation ( to one that satisfies Equation (T):
Theorem 2.1. Given algorithm ALG' such that ALG' O(f(s)) OPTIs O OPTIş, there OPT|s + 0gg) OPT]s-
exists an algorithm ALG such that ALG S +((((s))
The proof of this theorem, in Appendix [ is roughly the following: for every integer i, once the cost of the algorithm exceeds 2', we buy the cheapest predicted items of total cost at most 2', and then remove them from the prediction. While 2' OPT, the total cost is 0(1) OPT; once 2 exceeds OPT, the size of the prediction is at most SA. and Equation (6) implies Equation
Monotonicity, An additional, natural property that we demand from constituent algorithm in smooth combination framework is that increasing the penalty of input requests does not decrease the cost incurred by the algorithm. This is stated formally in the following definition.
Definition 2.2. We say that a prize-collectng algorithm ALG is monotone if, fixing the input request k-1 and current request (qk, Tx), then increasing TV does not decrease A TT). prefix ((g,, n4) /
Online amortization. Our framework extends to the where Lagrangian subset-compettiiiveesss and monotonicity are satisfied by amortized costs instead of actual costs. This is important because for some problems, the actual cost expressly prohibits subset competitiveness. For example, consider facility location: given an input of multiple, identical requests with very small penalty, the algorithm should eventually stop paying penalties and open a facility. However, for the specific request upon which the facility is opened, the cost of the algorithm is much larger than the penalty for that request, the latter being optimal for just that request. To overcome this complication, we allow the cost for request to be amortized over previous requests, and call this online amortization.
First, we define online amortization of costs, and define "monotone" online amortization which can be used in our framework.
Definition 2.3 (online amortization). Let @ = ((q1. (qn, xn)) be an online input given to ALG. An online amortization or OA is a number sequence (OA(g. T)) (). such that:
1. ALG(Q) S Eig,zie OA(g. R).
2. OA(gi, ni) is only function of (91, (gi. mT), and can thus be calculated online.
5

---

When considering the amortized cost of an algorithm, we use similar notation to the actual cost: on an imput Q, we use (A(@) to denote the total amortized cost. We also use QA(Q"l to denote the total amortized cost incurred on a request subset Q' S Q. In addition, for request (q. π) in the input Q. we use OA (q, x) to refer to the amortized cost of (q. here the input Q is clear from context.
Definition 2.4 (monotone online amortization). We call an online amortization OA monotone if (a) fixing previous requests, increasing the penalty of request (q. π) never decreases OA X), and (b) when the algorithm pays penalty for (q. r) then OA(q. 2
The Main Theorem We are now ready state the main theorem of our algorithmic framework. We use B1 and B2 to denote the competitive ratios of ALG and ALG2; the reader should think of Bi as O((()) and BI as (()(n)), i.e., B2 * Bi.
Theorem 2.5. Consider any online covering problem with predictions P. Let ALG,, ALG2 be two algorithms for the prize-collecting version of with monotone (online amortized) costs OA₁, OA2 respectively such that (a) ALG; is Lagrangian ji-subset-compeetine using OA1 w.E.t. the prediction cuubse-competitiv using OA2 (against general OPT).
S. and (b) ALG is Lagrangian
Then there exists ALG for P such that for every partition of the input Q into Q1, Q2 we have ALG(O) s 0(B)) (PTs( + OPT(Q2)
We later show that Theorem 2.5
implies Equation 6 for facility location and set cover.
3 Online Facility Location
In this section, we consider metric, nonuniform facility location with predictions and present a novel prize-collecting algorithm TREEPROXY. This algorithm is Lagrangian
w.r.t. the prediction S of possible facilities; thus, it is used in our framework to prove Theorems D.2 D.3) which in turn imply Theorems I.I 1.2 respectively. In addition, TREEPRONY is a result independent of our framework/predictions the competitiveness guarantee shown for TREEPROXy also achieves O Oloog m) competitiveness where m [X] is the size of the metric space. We prove the following theorem:
Theorem 3.1. For facility location with predictions, there exists randomized prize-collecting algorithm ALG with a monotone online amortization OA which is Lagrangian O(log) Subsess competitive using OA w.r.t S.
3.1 The Algorithm
Weighted hierarchically-sseaaree
trees (HSTs). The algorithm starts by embedding the metric space into the leaves of weighted 3-HST, a metric space in which edge weights decrease at least exponentially as one descends from the root.
Definition 3.2. For y > 1, a rooted tree with weights to the edges is a weighted y-HST if for every two edges é1, e2 such that e2 a parent edge of e1, it holds that c(e2) 2 ye(e1).
The following result is often used for embedding general metric spaces into weighted HSTs; involves composing the embeddings of Takcharoenphol et al. [17] and Bansal al. [12].
Theorem 3.3 (Due to 17) and (12)). For every metric space (X, ô) and constant y, there exists distribution D over weighted y-HSTs of depth (log) XI) in which the points in X are the leaves of the HST, such that for every two points X1.X2 E X we have:
1. 6(x1,x2) (x(,)))2) for every T in the support D.
2. ()- Ollggl)) 6(x1,x2).
The algorithm starts by embedding the induced metric space of into a weighted HST using Theorem 3.3 T denotes the resulting tree, and r denotes its root. For each edge E T, we denote by c(e) the cost of the edge e. Denote the set of leaves the subtree rooted at by L(v); note that L(r)= S. Denote the distance between two nodes u, in the tree by Ö7 v). For every point a X, define p(u)= := arg minwes 8(u, u'); ; that is, (u)) the closest predicted point u (abusing notation, similarly define p(q) for request q).

---

Proxy list. After embedding S into the leaves of a tree, the algorithm must open facilities on those leaves to serve requests. Intuitively, at any point the algorithm considers some (possibly internal) node E T. and considers connecting the current request through v to a facility in L(v). Choosing from I.(v) introduces tradeoff between the cost of opening the facility and its distance from v. For every v, we identify the leaves in L(v) which offer the best points in this tradeoff (i.e., Pareto frontier), and only allow the algorithm to choose from these leaves. This subset is called the proxy list of v. and denoted P(v) S L(v).
We now define the proxy list P(v). For ease of notation, define the logarithmic class operator f(x) == [logx]. For node E T, we construct the proxy list P(v) S L(v) as follows:
1. Start with -()).
2. While there exist distinct v1, V2 E V such that ((or)) 2 {(or) and ((ōT(V, z ((6r(v, remove vi from V.
3. Output V as P(v).
We denote by k(r) the size of the proxy list P(v). We order the proxy list of v by increasing facility cost, thus writing P(v) (s"..... ..())) For every v,i, we use the shorthands of := osp" and Slightly abusing notation, for every node v e 7 we define c(v) == c(e.) where e, is
of := öz the edge connecting v to its parent node (for r, we define c(r) = oo). For more streamlined notation, for every node E T we define 8 == c(v) and o" k(r)+1 co.
s,). (v.
Observation 3.4. For every node v E T, the proxy list P(v) satisfies:
1. For every L(v), there exists index i such that {(o)) ((ow) and ((6)) ((ō((v.)).
2. For every distinct 1 s k(v) + 1, it holds that {(O)) {(o').
3. For every distinct 0 s < (v), it holds that ((6)) ((6))
When i the third item in Observation 3.4 uses the fact that T is weighted 3-HST: thus, the cost of an edge is at least twice the distance from the child node of that edge to any descendant leaf.
Counters. For every node and every E (1....<vv) 1), we define a counter 1(v, of size o..
Algorithm description. The algorithm for facility location with predictions given Algorithm Initially, the algorithm embeds the metric space induced by S into a weighted 3-HST T, using Theorem 3.3; upon each node this T the proxy lists are computed, and the corresponding counters assigned. Upon the release of a request (q. π), the function UPONREQUEST is triggered. Upon receiving (q, n), it maps the request to the closest point p(q) in S (that is, a Icaf of the HST). Then, the algorithm attempts to solve the request on the HST through process of increasing counters, which we soon describe. (While the described algorithm raises these counters continuously, the process can easily be discretized, replacing the continuous growth with jumping discretely to the next event.) The algorithm keeps track of (some measure of) the cost involved; if during UPON ReQueST that amount exceeds the penalty лI, the algorithm pays the penalty instead (see Line 9
When solving the request on u = p(4), the algorithm climbs up the branch of u, until facility is found (or opened) to connect и. At each ancestor of the algorithm invests a growing amount T, in advancing the proxy list of (i.c.. buying a facility in P(v) closer to v). It raises the counter for the next item the proxy list until full, which point the relevant proxy facility is opened, and the next counter in the proxy list begins to increase. (Note that the same facility can be "opened" more than once due to being on multiple proxy lists.) Once T, reaches the cost of connecting to an open proxy, the algorithm stops increasing counters and makes the connection. When no proxy in P(v) is open, it could be that T, exceeds the cost of moving from to its parent pvv); in this case, we ascend the branch and explore proxies for pvv). Note that the function UPON of Algorithm 2 also returns value; this return value is the online amortization cost of the request, be used in the analysis of the algorithm. (See Figure [ for an example.)
The analysis of Algorithm 2 and the proof of Theorem appear in Appendix A
7

---

Algorithm 2: TREEPROXY for Prize- Collecting Facility Location with Pre- dictions
Initialization
Embed the prediction S into a weighted
3-HST 7 using Theorem 3.3
For For every v E and every
+ 1), set ((v,i) - O.
For every 7, set ((v) e-
Event Function UPONREQUEST(Q.I)
// Upon the next request q with penalty x in the sequence
possible state of Algorithm immedi- ately before connecting a request q. Here, has been mapped which is the closest point in S. The variable ancestor of и, is shown, is proxy list sy sg. The counters
Figure I:
Define u, p(g).
Define r 0, 0
continually increase t, r"
A(v.1(v) 1) at the same rate until: 6 q) 2 then // cost for request exceeds penalty; pay penalty instead. Pay the penalty x the request. return + π. // return amortized cost.
proxy list are also shown: 2(v, 1) is full (and a facility thus exists in s,), and A(v, 2) partial (the last counter to be raised han- dling q). At some point, the growth in the counters of exceeded the distance from to si and thus the connection of to sj is made.
10
11
12
if A(v, + (iyy)+1 then // counter for next proxy full; open facility at proxy.
13
Open facility at s *f(v)41*
Algorithm 3: Online Prize-Collecting
Fractional Set Cover
14
Increment (v))
15
goto Line 8
Initialization
Set x5 - 0 for every set
16
r 2 r(P) then
17
(f) = then
Event Function UPONREQUEST (q,
Set yq 0. 5 while L.(U(g)) Xs s do
// escalate the request to parent node.
Set < pvv).
Detine 0.
Set Y' Yy +1
if Yy then
20
goto Line
8
Pay penalty for q. return OA(g. x)= = 3x.
21
Connect to (/() // connect request to
9
closest proxy. return + (u. g)). return amortized cost.
foreach U(g) do
22
Ix Xx (1+ d ((t))e
n
return OA(g. 2yg-
4 Online Set Cover
In this section, present and analyze algorithm for prize-collecting fractional set cover which uses the well-known multiplicative updates method, and show that it Lagrangian subset-competitive Using this algorithm together with Algorithm[]]g yiilld Theorem I.3 (the proof appears in Appendix [
Preliminaries. In prize-collecting fractional set cover, we are given universe with elements and sets U; we define == JU]. A solution may fractionally buy sets, according to cost function c. Requests then arrive online, where each request for covering some element E E, which is contained in some subfamily of sets from U. To cover element, algorithm must hold fractions of sets containing e which sum to least 1. Observe that fractional set cover with predictions conforms to the definition of an online covering problem with predictions; in this problem, the items are the sets. For prize-collecting fractional set cover, we prove the following theorem.
Theorem 4.1. There exists a deterministic algorithm ALG for price-collecting fractional set cover that ALG Lagrangian O (log m) subset-comppeitne
Theorem implies that, in the framework of Algorithm our algorithm can be used as the general component, independent of the prediction. But, given prediction S U, can simply restrict the

---

family of sets used by the algorithm to the given prediction, yields an algorithm competitive against SPTs. Thus, Theorem 4.1 limeediately yields the following corollary.
Corollary 4.2. There exists deterministtic algorithm ALG for prize-collecting fractional set cover such that ALG is Lagrangian ( m "'llogmm)subsseee cerpuubeee-compttiiii w.r.t. prediction S S U. where [S] = m'.
The Algorithm. The algorithm for prize-collecting set cover is given in Algorithm 3 The algorithm follows the standard multiplicative updates method: while the pending request is uncovered, sets containing that request are bought at exponential rate (see 22 15 D. However, in this prize- collecting version, the algorithm never lets cost for a specific request exceed its penalty. For ease of notation, define (q) to be the collection of sets containing q: that is, U(q) == {s Ulq E s).
Analysis. Where the input Q fixed, and for (q. Q, we use ALG π as a shorthand for ALG(((q, x)) i.e. the cost of ALG when handling the request (q. π) as part of Q. We prove the two following lemmas:
Lemma 4.3. For every (q. E Q. it holds that ALG(q, S 3x.
Lemma 4.4. For every subset Q' Q, we have ALG(("1Q) O(log m) OPT(Q") where Q' is the
input formed from Q'.
These two lemmas imply penalty-robust subset competitiveness, property shown in Proposition C.2 to be equivalent to Lagrangian subset-compp cobbstt-comptttiivnessss. Thus, we focus on proving these lemmas; note that the proof of Lemma appears in Appendix
Proposition 4.5. In every iteration of UPONREQUEST( x), it holds that the total buying cost is at most 2yg. where yq the final value of the variable of the same name.
Proof. Consider each time yq is incremented. The total cost of buying sets is the following.
Σ cs. xEU(g)
- = 1+
Σ xs S2
Cs [((g)les)
xEU(g)
where the inequality due to the fact that Exet(ig Xs S 1. Thus, each time yg is incremented by 1, the cost of buying sets is at most 2, completing the proof.
Proof of Lemma 4.3 Consider UPONREQUEST(Q..1) x). it returned through Line it holds that
Yg 3 Proposition 4.5 shows that the total buying cost thus at most 2n, and this cost is also ALG(q, .T. Otherwise, the function returned through Line 8 in this case, since yg was incremented immediately before comparing Y4 π, the argument from the proof of Proposition 4.5 jiplies that the total buying cost at most 2(yg - 1) (using the final value of yq). In turn, this is at most 2x. In addition, the algorithm paid the penalty of π; overall, AL.((g, S 3x.
Proof of Theorem Lemma and Lemma 4.4 show that the algorithm is O(log m) PPRSSC Proposition C.2 then yields that the algorithm is Lagrangian Ollog m) -ubset-tccoomeeeiiieee
5 Experiments
Input Generation. Our set cover instances contain 100 elements. (The number of sets will vary in the experiments.) Every set contains every element with some constant probability (we choose = 0.02); that is, the input is represented by a random bipartite graph in which each edge manifests independently. Since this may not cover every element, we also add singleton sets for all elements. We generate random costs for the sets, independently drawn from a log-normal distribution (μ 0, 1.6). For given input, we generate a prediction in the following way:
1. Using an LP solver, we obtain an optimal fractional solution to the problem instance.
2. We randomly round the solution, such that every set appears in the prediction with probability proportional to its value in the fractional solution.
3. We apply noise to the prediction, of two types: false- poset-osstvve noise, which every set is added to the prediction with some probability p; and false-negative noise, in which every set removed from the prediction with some probability q. (The reader should think of p and q the classification error where the predictions were generated using classifier.)

---

ON
PREDON comp.
BASEMERGE
SMооTHMEROE tomp.
23
P.9
comp.
comp
20
6.007
1669 (0.070)
3.102 (0.565)
(0.122)
0,0.15
6.007 (0:244)
(54.466
6.246
3,820 (0.555)
0,0.3
6,007 (0.244)
96.156 (76.1977
7.093 7.095(1.355)
4.834 (1.687)
0,005
6,007 (0:244)
15:955 (30.2944
1,989 (0. 106)
3.648 (0.63))
3.251 (0. 184)
4,200 (0.534)
10
0.005,
6,007 (0.244)
(43.35
7.545
5.120 (0.642)
0.02, 0
6.007 (0.244)
2.631 (0) 154)
4,489 (0.660)
4,240 (0.266)
0.02 0.15
6.007 (0.244)
10.555 (7.549)
7,007 (1 A96)
5,024 (0.498)
0.0,
6,007 (0.244)
(9.549)
(1.33)
5,700 (0.509)
#546
Table 1: Competitive ratios for varying p.g. in "mean (standard deviation)" format. Best values in each underlined.
Figure 2: The competitive ratio for
varying numbers of sets.
4. Finally, add the singleton sets to the prediction, to ensure that the prediction covers all elements.
Baselines and evaluation. We evaluate our algorithm described in Section 4 denoted SMOOTIMERGE, against three baselines: the standard online algorithm without predictions, denoted ON; the online algorithm restricted to predicted sets, denoted PREDON; and the standard merging BASEMERGE of those two algorithms, which alternates between ON and PREDON whenever the overall cost doubles. For every choice of parameters, these costs are then averaged over 300 different random inputs. We then measure the expected competitive ratio of each algorithm. Our experiments were
measure the costs of the four algorithms;
an AWS EC2 r5. 16xlarge machine.
We ran the following experiments: (a) we vary the false-positive rate p and the nelet-ne rate q keeping the number of sets fixed at 10000 (Table and (b) we vary the number of sets in the input, fixing p 0.005. q = 0.15 (Figure 2)
Experimental Results. We ran two sets of experiments. In the first experiment, we varied the false- positive rate p and the false-negative rate q keeping the number of sets fixed at 10000. The results are reported in Table I We note that our algorithm SMOOTH outperforms the standard merging algorithm BASEMERGE and the online algorithm without predictions ON consistently across all values of q. SMOOTHMERGE also outperforms PREDON, the online algorithm restricted to the prediction, except when there are no false negatives, i.e., q O. This to be expected because O implies that there is a good solution contained in the prediction. When q > O, PREDON fails miserably and our algorithm SMOOTHMERGE obtains a competitive ratio that is an order of magnitude better than PREDON. This demonstrates the lack of robustness of PREDON because it is specifically tuned to correct predictions.
In the second set of experiments, we varied the number of sets in the input fixing the noise rates 0.005, q = 0.15. The results are reported in Figure [ Our algorithm SMOOTHMERGE consistently outperforms all the baseline algorithms. In particular, it is able to utilize predictions to outperform ON, which the standard merging BASEMERGE is unable achieve. Moreover, as the number of sets in the input grows, the gap between the two merging solutions increases.
6 Discussion
In this paper, we presented novel framework for smooth interpolation between robustness and consistency guarantees in facility location. More broadly, predictions for online algorithms are of two forms: prediction of the input and that of the solution. The notion of discrete-smoothness applies to any online combinatorial problem in the latter category, i.e., where solution provided in the form of a prediction to the algorithm. Many problems have been considered in this model including rent or buy problems, scheduling, matching, graph problems, etc. For all of these problems, the discrete-smonde smoothness framework alleviates the need for problem-speciee common framework for arguing about the gradual degradation of solution quality with increase in prediction error. We hope that the current work will streamline the desiderata for online algorithms by adding this prohlem-independent notion of smoothness to the established (and also
online algorithms, and applied it to set cover and
notions of prediction error and instead gives
properties of consistency and robustness.
10

---

Acknowledgments
YA supported in part by the Israel Science Foundation (grant No. 2304/20). DP supported in part by NSF awards CCF-1750140 (CAREER) and CCF-1955703.
References
[1] Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Perey Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 1661-4673. 2021.
[2] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Anmual ACM Symposium Theory of Computing, June 9-11, 2003, San Diego, CA. USA, pages 100-105. ACM, 2003.
[3] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM J. Comput., 39(2):361-377 2009.
[4] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 582-598. PMLR, 2022.
[5] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ML predictions for online algorithms. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 303-313. PMLR, 2020.
[6] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. On- line metric algorithms with untrusted predictions. In Proceedings of the 37th International Conference on Machine Learning, 2020, 2020.
[7] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev, Secretary and online matching problems with machine learned advice. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Lin, editors, Advances in Neural Infor- mation Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[8] Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposiun Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1070-1080. ACM, 2021.
[9] 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 Discrete Algorithmss, SODA 2022, Viruaal Conference / Alexandria, VA, USA, January 9- 12, 2022, pages 35-66. SIAM, 2022.
[10] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[11] Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dusl method for learning augmented algorithms. Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.

---

[12] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic- competitive algorithm for the k-server problem. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October pages 267-276. TEEE Computer Society, 2011.
22-25, 201
[13] Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vec. Scale-free allocation, amortized convexity, and myopic weighted paging. CORR, abs/201 1. 1.09766, 2020.
[14] Giulia Bernardini, Alexander Lindermayr, Alberto Marchetii-Spaccanlla, Nicole Megow, Leen Stougie, and Michelle Sweering. A universal error measure for input predictions applied to online graph problems. In NeurIPS, 2022.
[15] Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via primal-dual approach. Found. Trends Theor. Comput. Sci., 3(2-3):93-263, 2009.
[16] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages (09-429. ACM, 2021.
[17] 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. Special Issue on STOC 2003.
(18) Dimitris Fotakis. A primal-dual algorithm for online non-uniform facility location. J. Discrete Algorithms, 5(1):141-144, 2007.
[19] Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008.
[20] Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris. Learning augmented online facility location. CoRR, abs/2107.08277, 2021.
[21] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2319-2327. PMLR, 2019.
[22] Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[23] Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang. Online selection problems against constrained adversary. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 5002-5012. PMLR, 2021.
[24] Zhihao Jiang. Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted caching with predictions. In 47th International Colloquium on Automata, Languages, and Programming.
ICALP 2020, 2020.
[25] Ali Khanafer, Murali Kodialam, and Krishna P. N. Puttaswamy. The constrained ski-rental problem and its application to online cloud cost optimization. In Proceedings of the INFOCOM, pages 1492-1500, 2013.
[26] Jochen Könemann, Sina Sadeghian Sadeghabad, and Laura Sanità. An LMP ollog n)- approximation algorithm for node weighted prize collecting steiner tree. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA. USA. pages 568-577. IEEE Computer Society, 2013.
12

---

[27] Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving online algorithms via ML pre- dictions. In Samy Bengio. Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Dasa-BBanchh,, and Roman Garnett, editors, Advances in Neural Information Processing Sys- tems 31: Annual Conference on Neural Information Processing Systems 2018 NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 1684-9693, 2018
[28] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, Jamuary 5-8, 2020, pages 1877. SIAM, 2020.
[29] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance- robust 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 LIPIcs, pages 59:1-59:11 Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
[30] Russell Lee, Jessica Maghakian, Mohammad H. Hajiesmaili, Jian Li, Ramesh K. Sitaraman, and Zhenhua Liu. Online peak-aware energy scheduling with untrusted advice. In Herman de Meer and Michela Meo, editors, e-Energy '21: The Twelfth ACM International Conference on Future Energy Systems, Virtual Event, Torino, Italy, 28 June 2 July, 2021, pages 107-123. ACM, 2021.
[31] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmåsssnn Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3302-3311. PMLR, 2018.
[32] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice.
J. ACM, 68(4):24:1224:3) 2021.
[33] 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, 2001.
[34] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of L/Ples, pages 14:1-14:18. Schloss Dagstuhl- - Leibniz-7entrum für Informatik, 2020.
[35] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Rough- garden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020.
[36] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun. ACM, 65(7)333-35, 2022.
[37] Anna Moss and Yuval Rabani. Approximation algorithms for constrained node weighted steiner tree problems. SIAM J. Comput., 37(2):460 481, 2007.
[38] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML pre- dictions. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Sys- tems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018 December 3-8, 2018, Montréal. Canada, pages 9084-6689999 2018.
[39] Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi- shop ski rental with machine learned advice. In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 622 2020, virtual, 2020.
13

---

[40] Alexander Wei. Better and simpler learning-ausee augmented online caching. In Jaroslaw Byrka and Raghu Meka, editors, Approximattin, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of L.PIcs, pages 60:1-60:17. Schloss Dagstuhl Leibniz--Zentrum für Informatik,
2020.
[41] Alexander Wei and Fred Zhang. Optimal robustness- consssstey trade-offs for learning- augmented online algorithms. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Balcan, and Hsuan-Tice Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020.
[42] Chenyang Xu and Benjamin Moseley. Marming-augmenterr algorithms for online steiner tree. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposiun on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 March
2022, pages 8754-8752. AAAI Press, 2022.
14

---

We thus focus on A Analysis of Algorithm
For this analysis section, we fix any input Q (1)). An)) For both ALG and OPTs we use the superseript f to refer only to facility opening costs and to refer only to connection costs. We denote by (A(q. π) the value returned by EQuSR in Algorithm 2 upon receiving the pair (q, R); we choose (OA(q, ()) as the online amortization of Algorithm
Online Amortization. First, show that the cost of the algorithm is bounded by the online amortization:
Lemma A.1. It holds that ALG(O) & OA(())
Proof. We use the subscript y to refer to the final value of variable in UPONREQUIST(Q,.T) R)) The cost of the algorithm has the following three components:
1. Penalties paid.
2. Opening costs for facilities in S.
3. Connection costs for facilities S.
Let Q' S Q be the set of requests served by the algorithm (i.e., no penalty was paid).
Penalties for requests in Q(2'. Consider that whenever penalty is paid for request in Line 10 the additive term π appears in the amortized cost of that request. We charge the penalty cost to that term.
Opening cost. Note that facility s is only opened (at cost o²)) when the counter ((v, reaches of. and that counter is never used again; thus, the total opening cost can be charged to the sum over request of the amount by which request raises counters, which is Tq. We charge this to the term Tq in o). πτ)
Connection cost for requests in Q'. Suppose a request (q. E Q' connected some point S. There exists an index such that = s It holds that
(7) where the first and third inequalities are due to the triangle inequality, and the second inequality is due to the definition of My and Theorem 3.3 Now, note that dy ÖV(y. w) = 6,¹ s rq" [6]
8(q. w) (g. uq) + (ug. w) z S). 8y (Mg. w) 8(q, S) (ug. Vg) 6r (v.. w).
Vu from the condition of
Enumerate the path in the tree between Mq and Vig as Ug wn. W1, ... we Vq. and note that ör 6r(u Vg)) k-1 c(wj). Now, note that the variable advanced from wy to Wi+t due to Tq- w/ c(wj); thus, o7 ("g. vg) = Eyz "y Finally, note that Σ Tq" = Ty: combining, we get
>
ör (ug, vg) 6r(v.. s
1 =
f=0
Plugging the above into Equation 77 we get ((g, S + +5g. S). We thus charge the connection cost of requests from Q' to the (T, ((q (). 5)) term OA(q,
This completes the proof of the lemma.
Observation A.2. The online amortization OA of Algorithm 2 monotone.
Bounding Amortized Costs. Having shown that the online amortization is valid and monotone, it remains to bound the amortized cost of the algorithm. To show that the algorithm is Lagrangian it is enough to show that it is PRSC; see Proposition C.2 showing that the algorithm is PRSC using OA w.r.t.
From this point on, for every node v E T' and index i e [k(v) + 1]. we slightly abuse notation and use A(v,i) refer to both the counter itself, and its value at the end of the algorithm.
Proposition A.3 (Penalty Robustness). For every (q. Q. it holds that OA(g. x)) 2m.
15

---

Proof. If UPONREQUEST(Q..T Rτ) returns in Line 22 then it must be that the condition in Line 9 has failed, and thus T + 8(u q) & æ; thus, OA(q. π r (7 8 (u, q)) 2x.
Otherwise, UPONRFQUEST(Q. 7) returned on Line 11 in which case note that since r is raised continuously from 0, Line 11 ensures that completing the proof.
at all times. Thus, OA(q,
π 2n,
It remains show subset competitiveness for the algorithm. Henceforth, fix any subset of the input Q' C Q.
Proposition A.4. For every request q and E T, T s c(v).
Proof. Observe that T. cannot exceed 67 ((p))> for some current value of r(v), else the request is connected (or escalated to parent node). The fact that oj = c(v), together with the fact that 6 is decreasing sequence in i (Observation 3.4) complete the proof.
We now begin to bound the (amortized) costs of the algorithm. Recall that Q' is the input Q' with the penalties set to infinity; that is, the prize-collecting input converted to the standard setting, We would like to prove the following lemma.
Lemma A.5. B[OA(Q'10) s O(log((S)) OPTs O')
When the input consists of requests that are also from S, both the clients and facilities are from S, and thus on the leaves of the tree T. In this case, we define OPT, be any solution for the input under the metric space induced by the weighted HST T. To prove Lemma A.5 we first bound the cost of the algorithm against OPT, on a set of clients mapped their closest neighbors in S.
Lemma A.6. Let 2's be the input formed from Q' by mapping each request (q. xt) Q' the request (p(q), Rt. It holds that
oA(e'12) S
Σ 00) 0(1) OPT Q's)
(q.x)EQ'
Proof. First, observe both return statements in Algorithm and note that for every request (g. E Q it holds that
OA(q, Rt) s 2ny ((q. S).
(8)
We now focus on bounding Lgg.T)e Tq. i.c., total amount by which counters are raised when handling Q'. Let w be a facility opened in (2's) Let R = Q' be the set of requests such that their corresponding requests in 2s are connected by OPT, to the facility w. Using Observation 3.4 for every ancestor tree node of w, define i, to be the minimal index such that E(o%,) {(ow) and ((0%) ((rr(,,w)
Let P(w)= (vo w. VI, v2 r) be the path from to the root. The sum E(g.x)e Ty can be divided as follows:
1. Raising counters d(v,i) for P(w), S iy. The total amount here is most
Σ Σ vEP(W) Fm1
((v.)) s Σ
o
S
200
Σ vEP(w)
26 )+2
vEP(w) 7ml
iml
Σ
(((w))+2 +2
40w $ 4Dow
vEP(w)
PEP(W)
2. Raising counters ((r,)) for v Pww). Consider request 4 E R, and define u := p<(() = and to be the lowest common ancestor of u and w. The only nodes not in P(w) in which counters are raised when handling are on the path from u (inclusive) to v (non-inclusive). Using Proposition A.4 the total increase in counters for these nodes is at most öy (u, v).
16

---

3. Raising counters i(v.i) for v E P(w) and i > iv. Suppose that a request q raises such counter (v for some node V E P(w). When such counter is raised, the proxy $i., is already open, and thus the total raising of counters of index greater than iv, for vy by is at most 6", s -5 267 (v.. (1, v. w), where is the lowest common ancestor of and w. (Note that other proxies of vij of larger index could be open, but they can only be closer v. thus limiting the raising of counters even further.)
"/
Of those two costs, we would like to charge only for (v, (v, w), and charge (8 aggregate over all q. To do so, observe that the counters for nodes in Prw)\(r)) that were raised upon request q must be of the form A(v,, for v {vo..... .V.....VV-. .Vy-)-- q was repeatedly escalated from to v., the total increase in those counters must be at least 67(v, and thus 26y (v, v,) is upper bounded by twice the increase in those counters. However, seen in Item 1, over all requests, these increases sum at most wDow over all q E R; thus, the term 267 (v v) sums in aggregate to at most wD
(vy, v) in
As the request
Overall, denoting by w the lowest common ancestor of p(4) and w, we get:
Σ T(q. S 4Dow
Σ
5r(p(q).w9) w
8Dow
Σ (g.4)ER
67 w)
(g.z)ER
(g.z)ER
s 12Do + 26
Summing over all w, we get
Σ
<(q,x) & 12D O + OPTy (p))
(q.T)EQ'
Combining with Equation
we get
OA(C'10) s
Σ
8(q.5)+ + 24D OPT OPT; (Q's)
(q.x)EQ'
Having bounded the costs of the algorithm against OPT,, we can now prove Lemma A.5
Proof of Lemma
A.5
Using Lemma A.6
we get the following.
B[OA(Q'10) <
Σ
5) -
-00) (PT)
(g.x)EQ'
Now, note that every solution OPTs ( induces solution for 2s T, which opens the same facilities and makes the same connections (through the tree); the new tree solution has the same facility opening costs, and connection costs which are, in expectation, most O(lo(((S))- greater (see Theorem 3.3). Thus, we have
B B(OA(C'10) < Σ
6(g, S) (logg(())) OPTS O'') (q.z)E@'
Now, note that any solution OPT induces a solution for Q's of cost Eig (q. + OPTs @') and also note that L ōçg, S) is a lower bound for OPTs @ Plugging into the displayed equation above completes the proof of the lemma.
Proof of Theorem 3.7 Lemma A. Observation A.2 show that online amortization OA valid and monotone. Proposition A.3 shows penalty robustness, while Lemma A.5 shows subset competitiveness; thus, the algorithm is (log| using OA w.r.t. S. Using Proposition the algorithm is Lagrangian O S|) subset-compptitiie using OA w.r.t. S.
17

---

Algorithm 4: Variant of Fotakis' Algorithm for Prize-Collecting OFLP
Initialization
Let Q -
Let F - 0. For every X, let per -
Event Function UPONREQUEST(Q.TT Upon the next request q the sequence on point u
Set Q - (g)-
Denote by the closest open facility
Define Tq mnin(x,,(q, F), min x(o, p(v) Ō(g.
if rq F) then
10
[Connect q to the closest facility in F.
else if Fq = 0v pvv) ò v) for some X then
12
Open facility at v.
13
Connect 4 to v.
14
else
Pay the penalty for q.
16
(
17
return 2T, // return amortized cost
Function COMPUTEPOTENTIALS]
19
For every E Q, define Ay = ()(
20
For every location E X, set p(v) - Egeeldg ö(q. v))
B
Online Facility Location: The O(log n) - Competitive Algorithm
In this section, we present and analyze prize-collecting algorithm for facility location with predic- tions whose competitive ratio the number of requests 121. As is required for using Algorithm] 1 this algorithm is Lagrangian subset-competitive This algorithm based on the work of Fotakis [8 for the non non-prize-collecting setting. Specifically, we prove the following theorem.
Theorem B.1. For facility location with predictions, there exists a deterministic prize-collecting algorithm ALG with a monotone online amortization OA which Lagrangian O nubbeet- competitive using OA.
B.1 The Algorithm
Algorithm's description. This algorithm follows the main principles of Fotakis Fach point in the metric space has associated potential, such that when that potential exceeds the cost of opening facility that point, the facility is opened. This potential roughly translates to the amount by which the cost of the offline solution for known requests would decrease by opening facility at that location. Observing each request, consider the ball centered at that request such that the closest open facility lies the sphere of that ball; the request imposes a potential increase for every point inside that ball. However, as the requests now have penalties, these penalties cap the radius of ball, i.e., limit the potential imposed by the requests.
Specifically, the algorithm assigns each request cost Tg. which intuitively the minimum cost of handling the current request. This cost could be the penalty cost, the cost of connecting to open facility, or the cost opening a facility (beyond the current potential budget) and then connecting to it. The algorithm spends an amortized cost of Ty to serve 4, but potential ball of radius Ty is also created to serve future requests (at an future cost of most Ty).
For every x, we use x* as a shorthand for (O, . The prize-collecting algorithm based on 18 is given in Algorithm
B.1.1 Analysis
We now analyze Algorithm 4 and show that it proves Theorem B.1 For this analysis, we fix the prize-collecting input Q. Next, we define the online amortization OA such that OA OA(g, st) is the value returned by UPONREQUEST in Theorem B.I upon release of (q. E Q.
18

---

Online Amortization
We first prove that OA is valid and monotone.
Lemma B.2. The online amortization OA for Algorithm 4 is valid, i... ALG (A()).
Proof. For each request, observe the variable Tq. and note that:
If the penalty π is paid for q, then Tq = π.
. If q is connected to some facility, the connection cost of q does not exceed Tg-
It remains to bound the opening costs of the algorithm. Observe the evolution of the potential function Egeo min F). Fg as Q and F grow over time. This function is nonnegative, and grows by exactly Ty upon the release of (q. x) (after Line 8). Moreover, whenever facility at is opened (thus joining F),, decreases this amount by exactly oy. Thus, the total opening cost can be bounded by Σqe Ty-
Overall, we bounded the cost of the algorithm by Σ(g,))e 2Tg = =Lg OA(q,z).
Observation B.3. The online amortization OA given for Algorithm 4 is a monotone online amortiza- tion.
B.2 Bounding Amortized Costs
Having shown the necessary properties for the online amortization, we proceed to show that Algo- rithm ii Lagrangian subset-competitive using this amortization. As in Section first show that the algorithm is PRSC (see Proposition C.2 we begin by observing the penalty robustness of the algorithm.
Observation B.4. For every (q, Q, holds that OA(g, 2n.
We now fix the subset Q' S Q for the sake of proving subset competitiveness. Recall that Q' the standard input formed from the prize-collecting input Q' (by setting penalties to infinity).
Before proving subset-comppettiivenssss, we need to prove the following simple lemma.
Lemma B.5 (Min trace lemma). Let (a),..., .uk, (bi...., .u) be two sequences of non-negative numbers, and define Ct min(a;, by). Then if there exists such that for every it holds that Σ/ Cijj S then it holds that Σ Ci O(log -
Proof. We prove that E Cr S Hg by induction on k, where HA = Ex is the k-th harmonic number. Note that the base case, in which k holds as C1 $ z.
Now, for the general case, note that we can find such that Ci.i S E. then we can complete the proof by induction the sequences (a1,'.. Ad;-1, di+1. ,ax) and (bi..... ,b;-, b .bx). (Note that the constraints required for this inductive instance are implied by the original constraints.) This induction would imply that Σver CP,p H--1 which adding C₁ would complete the proof.
It remains to find i such C₁ S &. We consider the constraint Σ Ck.j S z. and observe the following cases.
Case 1: CR. are equal for all In this case, all CR. are at most }. In particular, this is true for Cy,K5 thus, choosing
completes the proof.
Ck.j are not all equal. In this case, observe that minimizes Ck and note that Ct.j 5 There exists j' such that Ct.j CR.j", which implies ck.j ag, and thus Ck.j bj. yielding by 5 But this implies Cjjj $ bj I I. and thus choosing == completes the proof.
Case 2:
We can now prove subset-coompetttiveness, stated in Lemma B.6
Lemma B.6. oA(2'12) s ((logl(')
19

---

Proof. Let w some facility opened by O and denote by R Q' the set of requests connected to that facility in OPT(P ( Define Cw E(q.))ER o(w, q) the total connection cost incurred by O on the facility w. Enumerate these requests as ((q1, ... (qx.. ma)), where R|. For S S k, denote by F; the set of facilities which were open immediately before the release of (qt, πT). As shorthand, we also define = Ty. Consider that the total potential of the facility can never exceed its cost Ow: moreover, upon release of (qi, Xi), the choice of T ensures that
Ow 2 - - w)+
-
7 8(gis
min(T).0(qi, Fi) ō(qi, w) 8(43. w) ō(qj.w)
21 - (7-5(gi.w) W)
mi w)) - 8 ((g.
j=1
2 -- 8(gi w) +
min(T,. Ö(qis w)) 2C
min 5qq, w)) 2C
where the second inequality uses the triangle inequality and the third inequality uses the definition of Tj.
From Equation D. we have that for every i S & holds that
Σ min(r,, - 5(q;, w)) s Ow 2C
Using Lemma B.5 this yields
Σ min(Tr, - w)) s O k) (ow + 2Cw)
Since 86(i; w) min Tú, 7 5(qi, w)), and since Σ 8(gi, w) Cw, have
Σ
s O(log k) (ow + C.) s Q'lgll(') (ow + Cw)
Finally, summing over all facilities w in OPT(2') yields
Σ Tq 0((og121))PP((2))
(g.n)EQ'
Proof of Theorem B.1
Through Lemma B.2 and Observation B.3 have that OA is valid and
monotone amortization for Algorithm Lemma B.6 and Observation B.4 then yield that the algorithm (log -PSS using OA. Using Proposition yields that the algorithm is Lagrangian Ollog Q) -subseet-competttive using OA, which completes the proof the theorem.
C The Smooth Combination Framework
C.1 Proof of Theorem 2.5
Proof of Theorem 2.3 Consider the framework in Algorithm applied to algorithms ALG1, ALG The framework ensures that all requests are satisfied, at least one of the constituent algorithms
20

---

serves each request. Denote by a(q) the final value assigned to the variable a upon request q: the prize-collecting imput given to both constituent algorithms is Q (lq. ()))) We define 2 2j be the partition of Q" induced by the partition of Q into Q1. Q2. As the algorithm only buys items bought by one of the constituent algorithms, its cost can thus be bounded by (LG We now bound ALG, (Q"); bounding (Q") is identical.
First, consider the prize-collecting solution which serves 2; optimally subject to using items from but pays the penalty for requests from Ø2 using the Lagrangian subset-compettiivenes of ALG against this solution yields
B B[ALG](Q') O(B)) OPTs( +B 0(1)
Σ a(q) qec:
(10)
Now, observe that using the definition of a and the fact that AL.G2 is monotone, we have that a(q)= S ALG2(q. a(4)); summing over requests in Q2 we get that Eqeo: a(q) 2 ALG)(D))0)))
Plugging into Equation (I0) we get
B[ALG] S ( (PT:(Q1)+ ALG2(0310")) I ( OPT) 0(3)) OPT(22)
where the second inequality uses the fact that ALG₂ is subset competitive to bound its cost on the subset Q; against the solution which serves those requests optimally. This completes the bounding of costs for ALG1; we can bound B[ALG;(Q*) in the same way. Summing the bounds for ALG, and ALG2, we get
ALG - O(Bi) (PTs((1)+ OPT(()))
which completes the proof.
C.2 Penalty-Robut Subset-Competittve Algorithms
In proving that a prize-collecting algorithm is Lagrangian subset-competiing (for use in our frame- work), we sometimes find it easier to prove that it penalty-robuss subset competitive, As now prove, this latter property is sufficient to prove the former. (In fact, it is easy to see that both properties are in fact equivalent.)
Definition C.1 (PRSC algorithm using online amortization). Let ALG be randomized prize- collecting algorithm equipped with an online amortization OA running on an input Q. We say that ALG is penalty-robust subset competitive (PRSC) using OA if both following conditions hold:
1. For every (q, Q we have OA(q, x) $ 0(1) π.
2. For every subset Q' c Q, we have B[OA(Q')Q)) 12)] s B- OPT(2))
(where Q' is the input formed from Q' by forcing service, i.c. setting penalties infinity.)
If in the second condition of PRSC we replace OPT @' by OPTs using OA w.r.t. Proposition C.2. A B-PRSC algorithm using OA (wert S) is also Lagrangian f--subset-compeltiiee using OA (w.r.. S).
Q' we say that ALG is B-PRSC
Proof. We prove this for general solution, restricting to S is identical. Consider prize-collecting input Q, and any subset Q' s Q. Let SOL be the optimal solution for Q', which pays penalties for 2, and serves 2,- Q' optimally. Then it holds that
B(oA(e'10)) =((o((2 (2)1 +B ON (e,10)]
s $ -B-OPT + +01)
Σ
(q.
=B SOL SOL"(('))))))) (10)SS(()))))
where the inequality uses both propertics of PRSC.
21

---

D Proofs of Theorems 1.1, and 1.3
We establish these theorems in three steps. First, combine various constituent prize-collecting algorithms using Theorem 2.5 and explicitly state the guarantees for the resulting algorithms. Then, we use these guarantees to derive the discrete-smoothnes property for the individual problems with respect to the size of the prediction (i.e., Equation (6)). Finally, we use Theorem 2.1 to make the competitive ratio depend [PT] rather than [S].
Before proceeding further, we need to precisely define the intersection//iffereeee of a solution with a prediction make Theorem I.I Theorem 1.2 and Theorem 1.3 completely formal.
Definition D.1 (restriction of solution with prediction). Consider an online covering problem with items & let S S & be some prediction. For every solution A which buys some items from &
Define Als be the solution which only buys items from S, the same amount as A.
Define Als be the solution which only buys items outside S, the same amount A.
Facility Location with Predictions. order to describe facility location as a covering problem, we must describe the set of items. Here, the set of items comprises an opening item b, for each facility and connection item Cv.q for each (request, facility) pair. When we informally write that S set of possible facilities, this can be formalized to the set of items by for E S, plus the connection items Cv.g for all q in the input and E S.
Due to Theorem 3.1 and Theorem B.1 we have that both Algorithm and Algorithm 4 can serve as constituent algorithms our framework. Combining both algorithms using Theorem 2.5 thus implies the following theorem.
Theorem D.2. For facility location with predictions, there exists randomized algorithm ALG such that for every input Q, and for every partition of Q into Q1, Q2, we have
B[ALG(Q)) s ((PT)) (PT)(Q1) O(log)22) OPT(22)
We obtain an additional result, which is useful for small metric spaces, from combining two instances of Algorithm 2 one for the entire metric space X and one for the predictions S.
Theorem D.3. For facility location with predictions, there exists a randomized algorithm ALG such that for every input Q, and for every partition of into Q1, Q2, have
B[ALG(0) s (1ogg(S(OPT) OPTs (2)) (logg OPT((2).
Consider solution OPT to facility location on a set requests Q. Partition Q into Q1, Q2 such that Qi contains all requests from Q that are connected facility in OPT (and Q2 is complementary). Using the algorithm ALG from Theorem D.2 we have
Proof of Theorem 1.7
(11) Now note that OPT|s a solution to Q1 that only uses facility and connection items from S, and thus OPTs(Q1) OPT Moreover, OPT | is solution to Q2, and thus OPTs OPT Plugging into Equation and noting that 1@2l S [Q], we get
ALG(Q) < (log[S)) OPTs O(lggl22) (P)(
ALG(Q) s (log Si) OPT]s + (logll)) OPT
We now plug the above equation into Theorem 2.1 thus replacing the dependence on [S] with dependence on [SPT]
Proof of Theorem 1.2 Identical to the proof Theorem [.] but using Theorem D.3
Set Cover with Predictions. Theorem 4.1 iiplies that Algorithm 3 I Lagrangian subset-competitive In addition, easy to see that Algorithm 3 monotone, as defied Definition 2.2] Thus, the algorithm can serve as a constituent algorithm in our framework. From combining two instances of Algorithm 3 Theorem 2.5 thus implies the following theorem.
Theorem D.4. For fractional set cover with predictions, with universe (E, U) and a prediction S S U, there exists a deterministic algorithm ALG such that for every input Q, and for every partition of Q into Q1 Q2, have
ALG(() O(log[S) OPTs(Qi) O(lgg(U) -
22

---

Using standard rounding techniques (see [5) for online set cover. we can round the fractional solution online at loss of (logl)).. In addition, we can then apply Theorem 2.1 replace [S] with [S(OPT]. Thus, Theorem D.4 yields the following corollary.
Corollary D.5. For (integral) cover with predictions, with universe (E, U) and prediction S S U, there exists a randomized algorithm ALG such that for every impus Q, and for every partition of Q into Q1, 22 we have
B B[ALG(O)] < log) OPTs((1) Olooll -
Proof of Theorem 1.3
set of requests Q. Partition Q into Q1. Q2 such that Qi contains all requests from Q that belong to set in OPT]s (and Q2 is complementary). Using the randomized algorithm ALG from Corollary D.5 we have
Consider solution OPT to set
ALG(Q) s O(log Q log]S)) (Qi) + O loglU) OPT(Q2)
(12)
Now note that OPTIs is a solution to Qı that only uses sets from S, and thus OPTs(Q1) SPTTs Moreover, O is a solution to Q2, and thus (Q2)(02) s OPT Plugging into Equation (12). we get
ALG(() < (llogl@) log|S) OPTIs
OPT|s
E Proof of Theorem 2.1 Reduction from Equation (6) to Equation
In this section, we give the proof of Theorem 2.1 whose goal give reduction from Equation to Equation (T). This replaces in the bound of Equation (6) with the term s6. where := OPT in order to obtain Equation
Proof of Theorem 2.7 Assume, without loss of generality, that the cheapest item in & costs 1, Con- sider the following construction of the algorithm ALG using the algorithm ALG':
Initialize i - 0, - - S, B - O, and define the item cost function c' < C. Let A be instance of ALG' with prediction set S", and cost function c'.
for incoming request q do
while True
Simulate sending to A, and let c be the resulting cost.
B + c then break
Spend 2' budget in buying the cheapest items S", let the bought subset items T.
Set - ST B < 0, < i+ For every e E T, set (e) - 0. Reset A to be c¹.
instance of ALG', given S' prediction, and using the (modified) cost function
n
Send to A, and set B - B
For integer (, define phase l be the subsequence of requests in which variable i takes value (. The cost of the algorithm can be charged to a constant times 2/, where j is the penultimate value of i in the algorithm. If 2/2 OPT, then the cost of the algorithm done. Henceforth, suppose OPT s 2/-1, Define Sy, Aj. d'j to be the values of the variables S', A and c' during phase j. When considering the cost of a solution relative to a cost function, we place that cost function as superscript (c.g.. OPT Before the beginning of phase the algorithm spent at least OPT budget on buying the cheapest items in the (remaining) prediction; thus holds that
most 0(1) OPT and we are
s s (SPT) Let qı.... 4k be the requests of phase j: moreover, let 9k+1 be the request upon which the variable i was incremented to 1. From the definition of qk+1. it holds that the cost of the instance of phase on (q1..... 9k- qk+1) is at least 2/; thus, the total cost of the algorithm can be charged to this cost, which denote by But, through Equation (6), and from the fact that
23

---

OPT is a solution which serves (q), { we have
a ((S(((((PP))) OPT 0z) OPT
s (((((S))PTT) 1PT]s 0(g) (OPT (s55))))))
s (((([S)PPT) -PT] (g) OPT|s
Proof of Lemma 4.4
Proof of Lemma 4.4 First, note that ALG((. Rt) s 3y4. where Yy is the final value of the variable of that name: Proposition 4.5 implies that the buying cost is at most 2yg. while penalty of x is paid
only if Æ Yq. We show that () Yg (log m). OPT(Q'); since ALG(q, π)) I 3 Yq. this would complete the proof of the lemma. Consider the (standard) primal and dual LPs for fractional set cover of Q' without penalties (i.e. solving Q*). The primal LP given by:
min Σ Xs c(s) such that Vq E Q': SEt
Σ sIgEs
Ks and Ys U Uxxx2 0.
and the dual LP given by:
max Σ
Y4 such that Vs U: Σ
Y4 c(s) and Vq Q' Y4 0.
giges
We claim that the dual solution { violates dual constraints by at most Ollgg m); thus, scaling it down by that factor yields a feasible dual solution, and a lower bound to OPT OPT(O').
Consider the dual constraint corresponding the s; want bound the term Σge@ iges Y'- Through induction on k, we can prove that once Ege@rlges Y4 = k for some integer k, it holds that
xy [1+ -1 Thus, once k O(c, log m) have and Eges N4 would increase more. This implies that scaling down {yo q by O(log m) yields feasible dual solution, which lower bounds OPT(Q)). and completes the proof.
remains to prove the inductive claim. For the base case where & = 0, the claim holds trivially. Now, assume that the claim holds for 1, and consider point in which Ege0rlyss Yy is incremented from k 1 to k; let x, x' be the old and new amounts by which is held in the algorithm. We have
x' =x |+ c(s) U(g)c(s) 2 m
[+ 1
1 c(s)
1
m [(++ c(s)
c(s) -
mc(s)
(13)
where the inequality uses the inductive hypothesis as well as the fact that (U(g)] s m.
24


Reviews:
[{"review_id": "lkV2Zf4UAd", "reviewer": "Reviewer_MB7r", "summary": "This paper presents the concept of \"discrete smoothness\" in the context of online algorithms with predictions. This notion smoothly bridges the gap between consistency and robustness, terms originally introduced by Purohit et al. For a class of problems called \"online covering problem\", the authors first show that a \"Lagrangian subset-competitive algorithm\" for the prize-collecting version of the problem can be transformed into an algorithm with discrete smoothness for the original problem. The paper then proposes Lagrangian subset-competitive algorithms for the prize-collecting versions of online facility location and online set cover problems, which are special cases of online covering problems. The effectiveness of the proposed algorithm is substantiated through numerical experiments.", "questions": "- Can you devise a Lagrantian subset-competitive algorithm for a general online covering problem?\n- The appropriateness of the term *discrete smoothness* is questionable. Several papers discuss \"smoothness\" for discrete problems and algorithms (without predictions; see, e.g., https://arxiv.org/abs/2211.04674). The concept you've proposed appears to be more focused on predictions rather than the discreteness of the problem. However, \"discrete smoothness\" doesn't inherently imply any association with predictions.", "limitations": "Yes", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Though I am not an online algorithms expert, I feel this paper includes many nontrivial arguments. The coined notion (discrete smoothness) is natural (except for the name; see Questions below). It is quite intriguing that a Lagrangian subset-competitive algorithm for the prize-collecting version can be transformed into an algorithm with discrete smoothness. Its proof is not straightforward. The algorithms for online facility location and set cover are also solid.", "weaknesses": "I was unable to identify any significant weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Here is our response:\n\n* We are unaware of a general construction that can encapsulate any algorithm for a covering problem and add the subset-competitiveness or Lagrangian properties. \n* The term “smoothness” has often been used in online algorithms with predictions to refer to a graceful degradation of performance as a function of prediction error (e.g., in [11]). We added the word “discrete” to differentiate between the smoothness guarantee we provide and existing, continuous notions of smoothness (e.g., where the prediction error involves continuous amounts, such as distances in a metric space). We appreciate the input regarding the naming choice, and will take it into account."}, {"review_id": "5xHNPHKX8M", "reviewer": "Reviewer_9LeQ", "summary": "Ideal learning-augment online algorithms should have the properties of \\emph{consistency} (meaning that they perform comparable to the optimum when the predictions are perfect) and \\emph{robustness} (meaning that they don't perform much worse than their classic counterparts even for arbitrary predictions) and should interpolate between these two regimes smoothly as the quality of the predictions vary (\\emph{smoothness}). The paper introduces a new form of smoothness guarantee called \\emph{discrete-smoothness} and achieve discrete-smooth algorithms for online facility location and set cover improving over previous work for these two problems. The definition of discrete smoothness is quite opaque to me but if the predictor predicts a solution $S$ we would like the algorithm to achieve a value of at most $O(f(s_\\Delta))\\cdot OPT(S) +O(f(n))OPT(\\overline{S})$ where  $OPT(S)=OPT\\cap S$, $OPT(\\overline{S})=OPT\\setminus S$, $s_{\\Delta}=|S\\cap OPT|$, and $f$ is the competitive ration without predictions. I can see how this makes sense if $S$ is, e.g., a \\emph{set} of points like for set cover or facility location. \n\nThe paper achieves these goals by designing algorithms for the prize-collecting variants of the problems (where the algorithms can choose to not include a vertex in set cover, or not serve a client in facility location at a penalty). It then combines these two algorithms by picking the minimum penalty such that the request is being served in one of the two algorithms. It finally 'buys' all items bought by either of the two algorithms. The first algorithm should have a better competitive ration of $O(f(s))$ but only on the restricted prediction $S$, the second one should have a competitive ratio of $O(f(n))$ 'against the unconstrained optimum OPT' which I am not sure what means. ", "questions": "l32: For a general combinatorial problem, it is very unclear what $OPT\\cap S$ means mathematically. Consider e.g, a matching problem where $S$ consists of  prediction of the degree of a node in a graph. Or the number of triangles that an edge is contained in for triangle counting. Notions like $OPT|_{S}$ seem to be overloaded with meaning (both $OPT\\cap S$ but also the cost of $OPT$ on $S$ (whatever that means for general problems)).\n\nl87: What is $m$?\n\nl123-124: What does 'against the unconstrained optimum OPT' mean?\n\nl126: What does it mean that $OPT|_S $ 'serves' a request? Is $OPT|_S$ part of the optimum solution? Is it a number? Same for l130\n\nl147: The definition of $ALG(Q'|Q)$ is unclear. It is unclear what it means that the algorithm addresses a subset of the input.\n\nl195: What does it mean that it has a 'monotone online amortization'? Hasn't been introduced and doesn't sound standard. What does it mean that it is $O(\\log |S|)$-subset competitiveusing OA w.r.t. S?\n\nl211: Theorem 2.3 is about the \\emph{expected} distance over the distribution. Do you pick a random tree to embed into?\n\nl232: What is $c(e)$?\n\nObservation 2.4: Should it have a proof? Is it easy? It seems correct but with the writing so unclear it's hard for me to tell.\n\nl252-254: What does it mean that it 'climbs up the branch', 'advances the proxy list', 'invests a growing amount'? Please, be more precise.\n\nAlgorithm 3: The while loop doesn't increase the $x_s$. Should it be an if and just increase $y_q$ to $\\pi$?\n\nLemma 3.3: Has $ALG(q,\\pi)$ been defined?\n\nLemma 3.4: How is 'the non-prize-collecting input formed from $Q'$' defined? \n\nl301: Line 11 doesn't seem to have a return. \n\nl329-330: What is the standard online algorithm without predictions? What is the online algorithm restricted to the predicted set?", "limitations": "None as far as I can tell", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "It is very interesting to obtain a better understanding of the consistency-robustness tradeoff as the quality of the predictions varies in learning augmented algorithms, so the paper is well-motivated. The definition of discrete-smoothness could have some merit.", "weaknesses": "First of all, the paper is quite poorly written and it is hard even to make sense of the definition of discrete-smoothness. I can see what the definition means for set cover and facility location. However, as a general definition for combinatorial problems, I don't think that it is that sensible. $OPT|_{S}$ appear to be both a number (the cost of the solution restricted to $S$) but it is also a set of points $OPT\\cap S$ (which by the way only seems to make sense in problems where the solution and prediction is a set of points). Even if the solutions are described as a set of points, is it necessarily the case that the cost is $|OPT\\cap S|$ (seems unlikely)? The paper makes an unsubstantiated that the notion applies to any combinatorial problem without specifying what is meant by a combinatorial problem either. Note that many algorithms with predictions don't actually predict solutions but properties of the input, e.g. the degree of a vertex in a graph.\n\n\nSolely considering the results and proofs for facility location and set cover, the paper is unfortunately written in a hand-wavy matter with informal definition and proofs. As written, it is impossible for me to verify that the results are  correct (I will provide a non-exhaustive list of examples below in my questions for the authors).\n\nAs such I think that the notion of discrete-smoothness could be relevant and that it touches upon important areas of research within learning-augmented algorithms. However, without a proper rigorous definition of discrete-smoothness and with a serious improvement in the write-up of the theorems, definitions, and proofs, I don't think the paper is in a state to be accepted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Here is our response:\n\nl32: We refer the reviewer to the example in the general rebuttal, which exemplifies what we meant by combinatorial problems, and how this notion captures the (min-cost, bipartite) matching problem. Note that in our paper we consider predictions which imply a set of variables (rather than the degree of a node). That is, a prediction would imply a collection of “recommended” matches.\n\n\nl87: $m$ is the number of points in the metric space. We see that it is mistakenly only defined in Line 192; we will add the definition to the introduction as well. \n\nl123-l124: The (unconstrained) optimal solution can use all of the items in the input. This is in contrast to the optimal solution that is restricted to using only predicted items, which is referred to in the previous sentence (Line 122). \n\nl126: The term $OPT|_S$ is overloaded to refer to both the set of items $OPT\\cap S$ and the cost of this set of items. While this notation overload is very common (e.g., for $OPT$ itself), we will modify the paper to make it explicit. \n\n\nl147: The input $Q$ is a sequence of requests that arrives one after the other. Upon each request, the algorithm must buy items such that the request is satisfied; this is what we call “addressing” the request. $ALG(Q’|Q)$ is thus the total cost incurred when addressing the requests of the subset $Q’$. \n\nl195: Online amortization refers to using an amortized cost for the steps taken by the online algorithm, rather than the actual cost. For some problems, such as facility location, subset competitiveness can only be shown w.r.t. this amortized cost.\nSpecifically, when the algorithm opens a new, expensive facility upon some request $q$, this is not subset-competitive relative to the singleton request set containing $q$. \nThus, a way of “spreading out” the cost of opening facilities over multiple requests is required – and this is achieved by online amortization. \nOnline amortization has also been used by [9] for a similar purpose. \n\nl211: Yes, the embedding is randomized, drawing a random tree from the distribution $\\mathcal{D}$ described in Theorem 2.3.\n\nl232: As defined in Line 212, $c(e)$ is the cost of edge $e$ in the given tree. \n\n\n\nObservation 2.4: The procedure in Lines 226-229 explicitly constructs a Pareto frontier from the leaves under $v$, in terms of the logarithmic class of facility opening cost and the logarithmic class of distance from $v$. In Observation 2.4, the first item simply states that every leaf $u$ is dominated by some element of the frontier; that is, there is a point in the frontier where the class opening cost is at most $\\ell(f_u)$, and the class of connection cost is at most $\\ell(\\delta_{u, v})$. Properties 2,3 of Observation 2.4 simply refer to the ordering chosen for the frontier (increasing facility cost, decreasing distance from $v$). \n\nl252-l254: This intuitive, verbal description of the algorithm is meant to accompany the formal description, which appears in Algorithm 2 as pseudocode. \n\nAlgorithm 3: Note that the “foreach” loop of Line 10, which does increase the $x_s$ variables, is included in the “while” loop.\n\nLemma 3.3: $ALG(q, \\pi)$ simply refers to the cost of the algorithm when addressing the request $(q,\\pi)$; we will add this definition to the paper. \n\nLemma 3.4: The non-prize-collecting input is formed from the prize-collecting input by using the same requests but without the option of paying penalties. We’ll clarify this in the paper. \n\nl301: The line references here seem to have been shifted by one, this reference actually refers to Line 12. This is also the case in Line 303, in which the reference is to Line 9 in the algorithm rather than Line 8. \n\nl329-l330:  The standard online algorithm without predictions refers to the algorithm of Theorem 3.1. The online algorithm restricted to the predicted set refers to the algorithm of Corollary 3.2. Equivalently, these are instances of the standard multiplicative-update algorithm for set cover, where all sets are allowed (Theorem 3.1) or when the algorithm discards unpredicted sets (Corollary 3.2). \n"}, {"review_id": "y6wxPIp52y", "reviewer": "Reviewer_h71T", "summary": "This paper studies online facility location and online set cover with predictions, and provides improved theoretical guarantees for these problems. The authors state that these improvements come from a new property that they call discrete-smoothness. Learning-augmented algorithms take as input a prediction on the input, and then use this prediction to make better decisions. For problems considered in this paper, it makes sense to think about the projection of a prediction onto an optimal solution, so one can decompose a prediction into the part whose projection hits a fixed optimal solution and the part whose projection does not. In my own words, that’s what the discrete-smoothness property is capturing.\n\nTechnically, the authors introduce a property they call Lagrangian subset-competitiveness, which is a property on randomized prize collecting algorithms that bounds the algorithms performance on all subsets of the input. The fact that facility location and set cover both satisfy this property is what unifies them to be studied in this paper, and then thrown into the discrete-smoothness framework.", "questions": "- (Please see question in Weaknesses, too)\n- Some of the language used is a bit outdated (or not in keeping with the majority) for learning-augmented algorithms. For instance, your use of “robustness” is what the community refers to as “competitive” and your use of “smoothness” is what the community refers to as robustness. I know you’re following the style of some previous papers (like the Bamas et al work), but the community has converged to the 3 terms of competitive, robust, and consistent.\n- The use of f() for the definition of discrete-smoothness and then f_v for the cost of opening a facility was a bit confusing, consider changing the variable of one?\n- Did any of the previous work in learning-augmented facility location look at non-uniform opening costs, or were you the first?\n- I’d say your statement that the Bamas et al work doesn’t satisfy any robustness property (in your definition of robustness) isn’t totally true. That work is interpolating between an offline and online algorithm based on a trust parameter, so in a sense the smoothness is in the trust parameter, which is some different type of measure of the error of the prediction.\n- ^ In fact, from this view, part of what I found satisfying about your work is that now you smoothness is parameterized by a much better quantity.\n- Your goal of hoping to define some more general, unifying framework for predictions is noble, but difficult. One line of work you might want to cite that has made some nice progress on this is by Sakaue and Oki. Check out their work on warm starts, if you aren’t familiar.\n- I might be dense here, but part of why the discrete-smoothness property doesn’t stick with me is because I don’t understand how you think about the projection when the optimal solution isn’t unique… any thoughts here? ", "limitations": "na", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Paper makes improvements on two learning-augmented problems. It is also worth noting that the assumptions on the settings are weaker in their work than in previous works.  In a sense, the results that existed for learning-augmented online set cover and facility location were a bit unsatisfying compared to what one should expect, so now the results seem up to par with what I would expect.\n- I found the Lagrangian subset-competitiveness very interesting technically. Bounding an algorithm’s performance on all subsets is quite strong and it’s cool the authors were able to make use of this property\n- Really clean writing.", "weaknesses": "- I don’t find the discrete-smoothness property technically impactful. The authors state it might be helpful as a general framework, but I think really what they found is that this Lagrangian subset-competitiveness property could be generally more useful. Do the authors have something in mind for when the discrete-smoothness property would be useful if an algorithm/ a problem does not satisfy Lagrangian subset-competitiveness? The only reason the discrete-smoothness property comes across as a weakness is because it’s highlighted a lot in the first 2 pages, so I was not really interested in the results until the third page. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Regarding the more semantic comments, we will be sure to implement the necessary changes. Here are our responses to the remaining questions: \n\n* Regarding the question in the Weaknesses section, the discrete-smoothness guarantee makes sense for many problems; see, e.g., our general rebuttal which demonstrates the scope to which this guarantee is useful. The concept of Lagrangian subset-competitive prize-collecting algorithms (and combining them) was introduced for the sake of obtaining discrete-smoothness for facility location and set cover; however, for other problems (e.g., matching) achieving discrete smoothness could require different techniques. (However, it is worth mentioning that Lagrangian subset-competitive algorithms also yield some smoothness property for general covering problems, beyond facility location and set cover; see Theorem C.5 in the supplementary full paper).\n\n* Some previous works on non-uniform facility location with predictions are those of Jiang et al. [22] and Azar et al. [9]. Those works consider different prediction models than those considered in our paper. \n\n* Regarding the Bamas et al paper, thanks for the comment, we’ll incorporate it into the paper. \n\n* Regarding the non-uniqueness of the optimal solution, as mentioned in the paragraph starting at Line 52, our bound applies for every choice of a feasible solution OPT. \nTo demonstrate why this is crucial, consider the case in which every item has two identical copies; in particular, this admits two optimal solutions OPT’,OPT’’ using the first and second sets of copies, respectively. Suppose the prediction is S=OPT’. Since OPT’’ is wholly unpredicted, If we insist on using OPT’’ in Equation (1), the bound becomes meaningless while the prediction itself is perfect.\n"}, {"review_id": "1p42IbPmtL", "reviewer": "Reviewer_mT48", "summary": "This paper studies online algorithms with predictions, in which a prediction is provided to the algorithm without any guarantee on its quality. On this topic, the general goal is to provide an algorithm which is (1) consistent (i.e. if the prediction is perfect the algorithm should be much better than a pure online algorithm), (2) robust (i.e. maintain a worst-case guarantee even if the prediction is arbitrarily bad), and (3) interpolate smoothly between the cases (1) and (2) when the prediction is neither perfect nor horrible. To obtain (3) we need to define an error metric to quantify how good the prediction is.\n\nIn this paper, the authors propose a general property that they call “discrete-smoothness” and gives discrete-smooths algorithms for online set cover with predictions and online facility location with predictions. This discrete-smooth property can be seen as a general error-metric for combinatorial problems in which the prediction is given in the form of a predicted solution.", "questions": "Line 86: I am not sure about the meaning of this comment “even for the online … (without predictions)….”. I thought Meyerson’s algorithm applied to the non-uniform case. Why are we comparing to Almanza in the case without predictions?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "It is nice to have one general definition of smoothness for many problems (although this definition has some issues, see below). This is an interesting conceptual contribution.", "weaknesses": "The techniques do not seem very novel. The combiner algorithm (Algorithm 1) is a variant of an algorithm that has been rediscovered repeatedly in the recent years in the context of algorithm with predictions. The prize-collecting set cover seems like an easy adaptation of the classical online set cover. Algorithm 2 seems a bit more technical but I am not sure the techniques are very novel either ([19] already uses HSTs for this problem as far as I know). \n\nIt is nice to remark that one can get a quite general smoothness like this but to me this smoothness seems a bit like avoiding the difficulty. In my opinion, a very interesting part of algorithms with predictions is to come up with a natural error-metric which is easy to understand and to relate the performance of the algorithm to this metric. With this new definition, we are left with Equation (1) which is clearly not so simple. Also, discrete-smoothness is indeed general but it requires the prediction to be a whole solution. This is kind of the most elaborate prediction one can make and is probably not learnable for many problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Here is our response:\n\n* Regarding the novelty of the combiner, existing combiners do not achieve our smoothness guarantee. The standard online combiner achieves a competitiveness bound of $O(min(ALG_1(Q), ALG_2(Q)))$, which could be arbitrarily worse than our bound. \nTo illustrate this, consider an input $Q$ in which ALG_1 suffers a cost of 1 on even-index requests and 1000 on odd-index requests, and ALG_2 suffers a cost of 1000 on even-index requests and 1 on odd-index requests. Both constituent algorithms would have a high cost on the input, of cost ~500 per request. This would also be the cost of a standard online combiner. However, our smooth combiner in Algorithm 1 would suffer a cost of ~1 per request. \n\n* Regarding the applicability of the discrete-smoothness notion, as mentioned in our general response, note that:\nDiscrete-smoothness has meaning regardless of the manner in which the prediction is delivered to the algorithm. For example, for set cover, the prediction could offer a “recommended” set for every arriving element; the family of sets offered over the input would then be the prediction $S$. \n\n* The prediction could be any collection of items; in particular, we do not assume that the prediction is a feasible solution to the online input.\nRegarding online facility location without predictions, note that $m$ in our bound is the number of points in the metric space, rather than the number of requests; thus, we compare ourselves to Almanza et al. who gave a guarantee in this parameter. Indeed, in their paper they show that despite being log-competitive in the number of requests $n$, Meyerson’s algorithm is as bad as $\\Omega(m)$-competitive.\n"}]

Author rebuttal:
We would like to thank the reviewers for their thorough reviews and thoughtful comments. We would like to clarify some aspects of the discrete-smoothness notion and its broad applicability.
The structure of many combinatorial problems is the following: one must assign binary values in {0,1} to a set of variables, such that the assignment satisfies some constraints, and incurs a cost which is a function $f$ of the variables to which 1 is assigned. Suppose one is given a prediction which induces any subset $S$ of these variables; then, the notion of discrete-smoothness in Equation (1) yields a bound which is a function of the affinity between OPT (the optimal subset of variables to which 1 is assigned) and the predicted subset $S$. Note the following: 
Discrete-smoothness does not dictate how the subset $S$ induced by the prediction is mediated to the algorithm. It could be that $S$ is simply given to the algorithm in advance; but, the prediction could also be a rule mapping a given request to the variables that should serve it, in which case $S$ is the union of suggested variables over the run of the algorithm. (For example, in set cover, the prediction could map an arriving element to the set that should be bought to address it.)
Discrete-smoothness does not demand that the subset induced by $S$ be feasible for the constraints induced by the input. Indeed, a possible use case in a real-world scenario would be to use a predictor that generates a solution for 90% of the arriving online input. 

Here is a concrete example, outside the scope of our paper, to which this notion could apply. In min-cost bipartite matching, the variables are of the form $x_{u,v}$, denoting the matching of node u with node v. A prediction would imply a set $S$ of possible pairs (not necessarily a feasible matching), and can be delivered, e.g., through a recommendation upon the arrival of a node (“match this node with one of $v_1, v_2, v_3$”).  
Another concrete example is Steiner tree, in which each variable represents buying an edge in the graph. 


Meta-review: The reviewer are divided regarding this paper. Reviewer h71T provides strong support for the paper's contributions and techniques. In contrast, Reviewers 9LeQ and mT48 are concerned about the presentation and the significance of the discrete smoothness definition introduced in the paper to bridge robustness and consistency in online optimization with learned predictions. Reviewer mT48 is also concerned about the novelty of the algorithms for the two main concrete problems addressed (set cover and facility location). The discrete smoothness definition is a new conceptual contribution that may lead to further progress. Additionally, the improvements obtained for the two problems considered (set cover and facility location) and the techniques involved are valuable contributions as well. For these reasons, I recommend accepting the paper.
Decision: Accept (poster)