14

# Online Algorithms with Multiple Predictions

Keerti Anand Department of Computer Science, Duke University, Durham, NC.
Email<EMAIL_ADDRESS>Rong Ge Department of Computer Science, Duke
University, Durham, NC. Email<EMAIL_ADDRESS>Amit Kumar Department of
Computer Science and Engineering, IIT Delhi, New Delhi, India. Email:
<EMAIL_ADDRESS>Debmalya Panigrahi Department of Computer Science, Duke
University, Durham, NC. Email<EMAIL_ADDRESS>
###### Abstract

This paper studies online algorithms augmented with multiple machine-learned
predictions. While online algorithms augmented with a single prediction have
been extensively studied in recent years, the literature for the multiple
predictions setting is sparse. In this paper, we give a generic algorithmic
framework for online covering problems with multiple predictions that obtains
an online solution that is competitive against the performance of the best
predictor. Our algorithm incorporates the use of predictions in the classic
potential-based analysis of online algorithms. We apply our algorithmic
framework to solve classical problems such as online set cover, (weighted)
caching, and online facility location in the multiple predictions setting. Our
algorithm can also be robustified, i.e., the algorithm can be simultaneously
made competitive against the best prediction and the performance of the best
online algorithm (without prediction).

##  1 Introduction

In many real world computational tasks, parts of the input are not known in
advance and are revealed piecemeal over time. However, the algorithm is
constrained to take decisions before the entire input is revealed, thereby
optimizing for an unknown future. For instance, when an online retailer has to
decide the locations of warehouses to serve clients, it does so without
precisely knowing how the clientele will grow over time. Similarly, in an
operating system, the cache scheduler has to decide which pages to evict from
the cache without knowing future requests for page access. These kinds of
scenarios are traditionally captured by the field of online algorithms, where
the algorithm makes irrevocable decisions without knowing the future. The
performance of an online algorithm is measured by its competitive ratio which
is defined as the maximum ratio across all inputs between the cost of the
online algorithm and that of an optimal solution (see, e.g., [BEY98]). While
this is a robust guarantee that holds for all inputs, the robustness comes at
the cost of making online algorithms excessively cautious thereby resulting in
strong lower bounds and also affecting their real world performance.

To overcome the pessimistic behavior of online algorithms, there has been a
growing trend in recent years to incorporate machine-learned predictions about
the future. This exploits the fact that in many real world settings, modern ML
methods can predict future behavior to a high degree of accuracy. Formalized
by Lykouris and Vassilvitksii [LV18, LV21] for the caching problem, the online
algorithms with prediction framework allows online algorithms to access
predicted future input values, but does not give any guarantee on the accuracy
of such predictions. (This reflects the fact that ML predictions, say
generated by a neural network, are usually without worst-case guarantees, and
can occasionally be completely wrong.) The goal is to design online algorithms
whose competitive ratio gracefully interpolates between offline algorithms if
the predictions are accurate – a property called consistency – and online
algorithms irrespective of predictions – a property called robustness (these
terms were coined by Kumar, Purohit, and Svitkina [KPS18]).

Online algorithms with predictions have been extensively studied in the last
few years for a broad range of problems such as variants of ski rental [KPS18,
KKP13, GP19, WZ20, AGP20, WLW20], set cover [BMS20], scheduling [KPS18, WZ20,
BMRS20, LLMV20, Mit20, LMH+21, ALT21], caching [LV18, Wei20, JPS20, BCK+20],
matching and secretary problems [LMRX21, DLLV21, AGKK20, JLTZ21], metric
optimization [ACE+20, APT22, FGGP21, JLL+21, ACL+21], data structures [Mit18],
statistical estimation [HIKV19, IVY19, EIN+21], online search [AGKP21], and so
on.

In this paper, we focus on online algorithms with multiple machine-learned
predictions. In many situations, different ML models and techniques end up
with distinct predictions about the future, and the online algorithm has to
decide which prediction to use among them. Indeed, this is also true of human
experts providing inputs about expectations of the future, or other
statistical tools for predictions such as surveys, polls, etc. Online
algorithms with multiple predictions were introduced by Gollapudi and
Panigrahi [GP19] for the ski rental problem, and has since been studied for
multi-shop ski rental [WLW20] and facility location [ACL+21]. Furthermore,
[BCKP20] considers multiple hints for regret minimization in Online Linear
Optimization. In our current paper, instead of focusing on a single problem,
we extend the powerful paradigm of online covering problems to incorporate
multiple predictions. As a consequence, we obtain online algorithms with
multiple predictions for a broad range of classical problems such as set
cover, caching, and facility location as corollaries of the general technique
that we develop in this paper.

#### The Online Covering Framework.

Online covering is a powerful framework for capturing a broad range of
problems in combinatorial optimization. In each online step, a new linear
constraint $\mathbf{a}\cdot\mathbf{x}\geq b$ is presented to the algorithm,
where $\mathbf{x}$ is the vector of variables, $\mathbf{a}$ is a vector of
non-negative coefficients, and $b$ is a scalar. The algorithm needs to satisfy
the new constraint, and is only allowed to increase the values of the
variables to do so. The goal is to minimize an objective function
$\mathbf{c}\cdot\mathbf{x}$, where $\mathbf{c}$ is the vector of costs that is
known offline. This formulation captures a broad variety of problems including
set cover, (weighted) caching, revenue maximization, network design, ski
rental, TCP acknowledgment, etc. Alon et al. [AAA+09] proposed a
multiplicative weights update (MWU) technique for this problem and used it to
solve the online set cover problem. This was quickly adapted to other online
covering problems including weighted caching [BBN07], network design [AAA+06],
allocation problems for revenue maximization [BJN07], etc. (The reader is
referred to the survey [BN09a] for more examples.) All these algorithms share
a generic method for obtaining a fractional solution to the online covering
problem, which was formalized by Buchbinder and Naor [BN09b] and later further
refined by Gupta and Nagarajan [GN14]. Since then, the online covering problem
has been generalized to many settings such as convex (non-linear) objectives
[ABC+16] and mixed covering and packing problems [ABFP13].

#### Comparison with Prior Work on Online Covering with ML Prediction.

Bamas, Maggiori, and Svensson [BMS20] were the first to consider the online
covering framework in the context of ML predictions. In a beautiful work, they
gave the first general-purpose tool for online algorithms with predictions,
and showed that this can be used to solve several classical problems like set
cover and dynamic TCP acknowledgment. In their setting, a solution is
presented as advice to the online algorithm at the outset, and the algorithm
incorporates this suggestion in its online decision making.

In our current paper, we give a general scheme for the online covering
framework with multiple predictions. In particular:

  1. –

Since we are in the multiple predictions setting, we allow $k>1$ suggestions
instead of just a single suggestion, and benchmark our algorithm’s performance
against the best suggested solution. (Of course, the best suggestion is not
known to the algorithm.)

  2. –

In contrast to Bamas et al. [BMS20], we do not make the assumption that the
entire suggested solution is given up front. Instead, in each online step,
each of the $k$ suggestions gives a feasible way of satisfying the new
constraint. Note that this is more general than giving the suggested
solution(s) up front, since the entire solution(s) can be presented in each
online step as a feasible way of satisfying the new constraint.

  3. –

In terms of the analysis, we extend the potential method from online
algorithms (in contrast, Bamas et al. [BMS20] use the primal dual framework).
The potential method has been used recently for many classic problems in
online algorithms such as weighted paging [BBN10], $k$-server [BGMN19], metric
allocation [BC21], online set cover [BGMN19], etc. In fact, it can also be
used to reprove the main results of Bamas et al. [BMS20] in the single
prediction setting. In this paper, we extend this powerful tool to incorporate
multiple ML predictions.

  4. –

Finally, we show that our techniques extend to a generalization of the online
covering framework to include box-type constraints. This extension allows the
framework to handle more problems such as online facility location that are
not directly captured by the online covering framework.

#### Comparison with Online Learning.

The reader will notice the similarity of our problem to the classical experts’
framework from online learning (see, e.g., the survey [Sha12]). In the
experts’ framework, each of $k$ experts provides a suggestion in each online
step, and the algorithm has to choose (play) one of these $k$ options. After
the algorithm has made its choice, the cost (loss) of each suggestion is
revealed before the next online step. The goal of the algorithm is to be
competitive with the best expert in terms of total loss. In contrast,

  1. –

Since we are solving a combinatorial problem, the (incremental) cost of any
given step for an expert or the algorithm depends on their pre-existing
solution from previous steps (therefore, in particular, even after following
an expert’s choice, the algorithm might suffer a larger incremental cost than
the expert). This is unlike online learning where the cost in a particular
step is independent of previous choices.

  2. –

In online learning, the algorithm is benchmarked against the best static
expert in hindsight, i.e., the best solution whose choices match that of the
same expert across all the steps. Indeed, it can be easily shown that no
algorithm can be competitive against a dynamic expert, namely a solution that
chooses the best suggestion in each online step even if those choices come
from different experts. Observe that such a dynamic expert can in general
perform much better than each of the suggestions, e.g., when the suggestions
differ from each other but at each time, at least one of them suggests a good
solution. But, in our problem, since the choices made by experts correspond to
solutions of a combinatorial problem, we can actually show that our algorithm
is competitive even against a dynamic expert. Namely, the $k$ suggestions in
every step are not indexed by specific experts, and the algorithm is
competitive against any composite solution that chooses any one of the $k$
suggestions in each step.

  3. –

In online learning, the goal is to obtain regret bounds that show that the
online algorithm approaches the best (static) expert’s performance up to
additive terms. Such additive guarantees are easily ruled out for our problem,
even for a static expert. As is typically the case in online algorithms, our
performance guarantees are in the form of (multiplicative) competitive ratios
rather than (additive) regret bounds.

#### Our Contributions.

Our first contribution is to formalize the online covering problem with
multiple predictions (Section 2). Recall that in each online step, along with
a new constraint, the algorithm receives $k$ feasible suggestions for
satisfying the constraint. Using these suggestions, we design an algorithm for
obtaining a fractional solution to the online covering problem–that we call
the ocp algorithm (Section 3). To compare this algorithm to the best suggested
solution, we define a benchmark dynamic that captures the minimum cost
(fractional) solution that is consistent with at least one of the suggestions
in each online step.

  * –

Our main technical result shows that the cost of the solution produced by the
ocp algorithm is at most $O(\log k)$ times that of the dynamic solution.

It is noteworthy that unlike in the classical online covering problem (without
predictions), the competitive ratio is independent of the problem size, and
only depends on the number of suggestions $k$. As the number of suggestions
increases, the competitive ratio degrades because the suggestions have higher
entropy (i.e., are less specific). As two extreme examples, consider $k=1$, in
which case it is trivial for an algorithm to exactly match the dynamic
benchmark simply by following the suggestion in each step. In contrast, when
$k$ is very large, the set of suggested solutions can essentially include all
possible solutions, and therefore, the suggestions are useless.

The analysis of the ocp algorithm makes careful use of potential functions
that might be of independent interest. But, while the analysis of the ocp
algorithm is somewhat intricate, we note that the algorithm itself is
extremely simple.

  1. –

We show that the competitive ratio of $O(\log k)$ obtained by the ocp
algorithm is tight. We give a lower bound of $\Omega(\log k)$ by only using
binary (0/1) coefficients and unit cost for each variable, which implies that
the lower bound holds even for the special case of the unweighted set cover
problem.

  2. –

Using standard techniques, we observe that the ocp algorithm can be
robustified, i.e., along with being $O(\log k)$-competitive against the best
suggested solution, the algorithm can be made $O(\alpha)$-competitive against
the optimal solution where $\alpha$ is the competitive ratio of the best
online algorithm (without predictions).

We then use the ocp algorithm to solve two classic problems–online set cover
(Section 4) and caching (Section 5)–in the multiple predictions setting.

  * –

We generalize the online covering framework by introducing box-type
constraints (Section 6). We show that our techniques and results from online
covering extend to this more general setting.

We then use this more general formulation for solving the classical online
facility location problem (Section 7).

##  2 The Online Covering Framework

###  2.1 Problem Statement

We define the online covering problem (ocp) as follows. There are $n$ non-
negative variables $\\{x_{i}:i\in[n]\\}$ where each $x_{i}\in[0,1]$.
Initially, $x_{i}=0$ for all $i\in[n]$. A linear objective function
$c(x):=\sum_{i=1}^{n}c_{i}x_{i}$ is also given offline. In each online step, a
new covering constraint is presented, the $j$-th constraint being given by
$\sum_{i}a_{ij}x_{i}\geq 1$ where $a_{ij}\geq 0$ for all $i\in[n]$.111A more
general definition allows constraints of the form
$\sum_{i=1}^{n}a_{ij}x_{i}\geq b_{j}$ for any $b_{j}>0$, but restricting
$b_{j}$ to $1$ is without loss of generality since we can divide throughout by
$b_{j}$ without changing the constraint. The algorithm is only allowed to
increase the values of the variables, and has to satisfy the new constraint
when it is presented. (We denote the total number of constraints by $m$.) The
goal is to minimize the objective function $c(x)$. We write this succinctly
below:

$\min_{x_{i}\in[0,1]:i\in[n]}\left\\{\sum_{i=1}^{n}c_{i}x_{i}:\sum_{i=1}^{n}a_{ij}x_{i}\geq
1~{}\forall j\in[m]\right\\}.$

This framework captures a large class of algorithmic problems such as
(fractional) set cover, caching, etc. that have been extensively studied in
the online algorithms literature. Our goal will be to obtain a generic
algorithm for ocp with multiple suggestions. When the $j$-th constraint is
presented online, the algorithm also receives $k$ suggestions of how the
constraint can be satisfied. We denote the $s$-th suggestion for the $j$-th
constraint by variables $x_{i}(j,s)$; they satisfy
$\sum_{i=1}^{n}a_{ij}x_{i}(j,s)\geq 1$, i.e., all suggestions are feasible.

To formally define the best suggestion, we say that a solution
$\\{x_{i}:i\in[n]\\}$ is supported by the suggestions
$\\{x_{i}(j):i\in[n],j\in[m]\\}$ if $x_{i}\geq x_{i}(j)$ for all $j\in[m]$.
Using this definition, we consider below two natural notions of the best
suggestion that we respectively call the experts setting and the multiple
predictions setting.

#### The Experts Setting.

In the experts setting, there are $k$ experts, and the $s$-th suggestion for
each constraint comes from the same fixed expert $s\in[k]$ (say some fixed ml
algorithm or a human expert). The online algorithm is required to be
competitive with the best among these $k$ experts222This is similar to the
experts model in online learning, hence the name.. To formalize this, we
define the benchmark:

${\textsc{static}}=\min_{s\in[k]}\sum_{i=1}^{n}c_{i}\cdot\max_{j\in[m]}x_{i}(j,s).$

Note that $\\{\max_{j\in[m]}x_{i}(j,s):i\in[n]\\}$ is the minimal solution
that is supported by the suggestions of expert $s$; hence, we define the cost
of the solution proposed by expert $s$ to be the cost of this solution.

#### The Multiple Predictions Setting.

In the multiple predictions setting, we view the set of $k$ suggestions in
each step as a bag of $k$ predictions (without indexing them specifically to
individual predictors or experts) and the goal is to obtain a solution that
can be benchmarked against the best of these suggestions in each step.
Formally, our benchmark is the minimum-cost solution that is supported by at
least one suggestion in each online step:

${\textsc{dynamic}}=\min_{\mathbf{\hat{x}}\in\hat{X}}\sum_{i=1}^{n}c_{i}\cdot\hat{x}_{i},\text{
where}$ $\hat{X}=\\{\mathbf{\hat{x}}:\forall i\in[n],\forall j\in[m],\exists
s\in[k],\hat{x}_{i}\geq x_{i}(j,s)\\}.$

Note that every solution that is supported in the experts setting is also
supported in the multiple predictions setting. This implies that
${\textsc{static}}\geq{\textsc{dynamic}}$, and therefore, the competitive
ratios that we obtain in the multiple predictions setting also hold in the
experts setting. Conversely, the lower bounds on the competitive ratio that we
obtain in the experts setting also hold in the multiple predictions setting.

###  2.2 Our Results

We obtain an algorithm for ocp with the following guarantee in the multiple
predictions setting (and therefore also in the experts setting by the
discussion above):

######  Theorem 2.1.

There is an algorithm for the online covering problem with $k$ suggestions
that has a competitive ratio of $O(\log k)$, even against the dynamic
benchmark.

Note that this competitive ratio is independent of the size of the problem
instance, and only depends on the number of suggestions. In contrast, in the
classical online setting, the competitive ratio (necessarily) depends on the
size of the problem instance.

Next, we show that the competitive ratio in Theorem 2.1 is tight by showing a
matching lower bound. This lower bound holds even in the experts setting
(hence, by the discussion above, it automatically extends to the multiple
predictions setting):

######  Theorem 2.2.

The competitive ratio of any algorithm for the online covering problem with
$k$ suggestions is $\Omega(\log k)$, even against the static benchmark.

We noted earlier that it is desirable for online algorithms to have robustness
guarantees, i.e., that the algorithm does not fare much worse than the best
online algorithm (without predictions) even if the predictions are completely
inaccurate. Our next result is the robust version of Theorem 2.1:

######  Theorem 2.3.

Suppose a class of online covering problems have an online algorithm (without
predictions) whose competitive ratio is $\alpha$. Then, there is an algorithm
for this class of online covering problems with $k$ suggestions that produces
an online solution whose cost is at most $O(\min\\{\log
k\cdot\text{{{dynamic}}},\alpha\cdot{\textsf{opt}}\\})$.

We will prove Theorem 2.1 in the next section. The proofs of Theorem 2.2 and
Theorem 2.3 are given in Section 3.2 and Section 3.1 respectively.
Subsequently, we apply the algorithmic framework developed in Theorem 2.1 to
obtain tight competitive ratios for specific instantiations of ocp, namely the
set cover problem (Section 4) and the caching problem (Section 5). Finally, we
extend our ocp result to include box-type constraints (Section 6) and apply it
to the online facility location problem (Section 7).

##  3 Online Covering Algorithm

Recall that in the online covering problem, the new constraint that arrives in
the $j$-th online step is $\sum_{i=1}^{n}a_{ij}x_{i}\geq 1$ and the algorithm
receives $k$ suggestions where the $s$-th suggestion is denoted $x_{i}(j,s)$.
If the current solution of the algorithm given by the variables $x_{i}$ is
feasible, i.e., $\sum_{i=1}^{n}a_{ij}x_{i}\geq 1$, then the algorithm does not
need to do anything. Otherwise, the algorithm needs to increase these
variables until they satisfy the constraint. Next, we describe the rules
governing the increase of variables.

Intuitively, the rate of the increase of a variable $x_{i}$ should depend on
three things. First, it should depend on the cost of this variable in the
objective, namely the value of $c_{i}$; the higher the cost, the slower we
should increase this variable. Second, it should depend on the contribution of
variable $x_{i}$ in satisfying the new constraint, namely the value of
$a_{ij}$; the higher this coefficient, the faster should we increase the
variable. Finally, the third factor is how strongly $x_{i}$ has been
suggested. To encode this mathematically, we first make the assumption that
every suggestion is tight, i.e.,

$\sum_{i=1}^{n}a_{ij}x_{i}(j,s)=1\text{ for every suggestion }s\in[k].$ (1)

This assumption is without loss of generality because, if not, we can decrease
the variables $x_{i}(j,s)$ in an arbitrary manner until the constraint becomes
tight. (Note that this change can only decrease the cost of the benchmark
solutions dynamic and static; hence, any competitive ratio bounds obtained
after this transformation also hold for the original set of suggestions.)

Having made all the suggestions tight, we now encode how strongly a variable
has been suggested by using its average suggested value
$\frac{1}{k}\cdot\sum_{s=1}^{k}x_{i}(j,s)$. Our algorithm (see Algorithm 1)
increases all variables $x_{i}$ satisfying $x_{i}<\frac{1}{2}$ simultaneously
at rates governed by these parameters; precisely, we use

$\frac{dx_{i}}{dt}=\frac{a_{ij}}{c_{i}}\left(x_{i}+\delta\cdot
x_{ij}\right),\text{ where
}\delta=\frac{1}{k},x_{ij}=\sum_{s=1}^{k}x_{i}(j,s).$

The algorithm continues to increase the variables until
$\sum_{i=1}^{n}a_{ij}x_{i}\geq\frac{1}{2}$; along the way, any variable
$x_{i}$ that reaches $\frac{1}{2}$ is dropped from the set of increasing
variables. To satisfy the $j$-th constraint, we note that the variables
$2x_{i}$ are feasible for the constraint. (Note that since all variables
$x_{i}\leq\frac{1}{2}$ before the scaling, every variable can be doubled
without violating $x_{i}\leq 1$.) Since this last step of multiplying every
variable by $2$ only increases the cost of the algorithm by a factor of $2$,
we ignore this last scaling step in the rest of the analysis.

0.1 Offline: All variables $x_{i}$ are initialized to $0$.

0.2 Online: On arrival of the $j$-th constraint:

0.3 while $\sum_{i=1}^{n}a_{ij}x_{i}<\frac{1}{2}$,

0.4 for $i\in[n]$

0.5 if $x_{i}<\frac{1}{2}$, increase $x_{i}$ by
$\frac{dx_{i}}{dt}=\frac{a_{ij}}{c_{i}}\left(x_{i}+\delta\cdot x_{ij}\right)$,

where $\delta=\frac{1}{k}$ and $x_{ij}=\sum_{s=1}^{k}x_{i}(j,s)$.

Algorithm 1 Online Covering Algorithm

Before analyzing the algorithm, we note that although we described it using a
continuous process driven by a differential equation, the algorithm can be
easily discretized and made to run in polynomial time where in each discrete
step, some variable $x_{i}$ reaches $\frac{1}{2}$ (and therefore, $x_{i}$
cannot increase any further) or $\sum_{i=1}^{n}a_{ij}x_{i}$ reaches
$\frac{1}{2}$ (and therefore, the algorithm ends for the current online step).
In this section, we will analyze the continuous algorithm rather than the
equivalent discrete algorithm for notational simplicity.

Next, we show that the algorithm is valid, i.e., that there is always a
variable $x_{i}$ that can be increased inside the while loop. If not, then we
have $\sum_{i=1}^{n}a_{ij}x_{i}<\frac{1}{2}$ but $x_{i}\geq\frac{1}{2}$ for
all variables $x_{i}$, $i\in[n]$. This implies that $\sum_{i=1}^{n}a_{ij}<1$,
which is a contradiction because the constraint $\sum_{i=1}^{n}a_{ij}x_{i}\geq
1$ is then unsatisfiable by any setting of variables $x_{i}\leq 1$. (In
particular, this would mean that there cannot be any feasible suggestion for
this constraint.)

Now, we are ready to bound the competitive ratio of Algorithm 1 with respect
to the dynamic benchmark. First, we bound the rate of increase of algorithm’s
cost:

######  Lemma 3.1.

The rate of increase of cost in Algorithm 1 is at most $\frac{3}{2}$.

###### Proof.

The rate of increase of cost is given by:

$\displaystyle\sum_{i=1}^{n}c_{i}\cdot\frac{dx_{i}}{dt}$
$\displaystyle=\sum_{i=1}^{n}a_{ij}\left(x_{i}+\delta\cdot x_{ij}\right)$
$\displaystyle=\sum_{i=1}^{n}a_{ij}x_{i}+\frac{1}{k}\cdot\sum_{i=1}^{n}\sum_{s=1}^{k}a_{ij}x_{i}(j,s)$
$\displaystyle<\frac{1}{2}+\frac{1}{k}\cdot\sum_{s=1}^{k}\left(\sum_{i=1}^{n}a_{ij}x_{i}(j,s)\right)=\frac{3}{2},$

where we used $\sum_{i=1}^{n}a_{ij}x_{i}<\frac{1}{2}$ from the condition on
the while loop, and $\sum_{i=1}^{n}a_{ij}x_{i}(j,s)=1$ for all $s\in[k]$ from
Equation 1. ∎

We now define a carefully crafted non-negative potential function $\phi$. We
will show that the potential decreases at constant rate when Algorithm 1
increases the variables $x_{i}$ (Lemma 3.4). By Lemma 3.1, this implies that
the potential can pay for the cost of Algorithm 1 up to a constant. We will
also show that the potential $\phi$ is at most $O(\log k)$ times the dynamic
benchmark (Lemma 3.3). Combined, these yield Theorem 2.1.

Let $x^{\textsc{dyn}}_{i}$ denote the value of variable $x_{i}$ in the dynamic
benchmark. The potential function for a variable $x_{i}$ is then defined as
follows:

$\phi_{i}=c_{i}\cdot
x^{\textsc{dyn}}_{i}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{i}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}},\text{ where }\delta=\frac{1}{k}.$

and the overall potential is:

$\phi=\sum_{i:x^{\textsc{dyn}}_{i}\geq x_{i}}\phi_{i}.$

The intuition behind only including those variables that have
$x^{\textsc{dyn}}_{i}\geq x_{i}$ in the potential function is that the
potential stores the excess cost paid by the dynamic benchmark for these
variables so that it can be used later to pay for increase in the algorithm’s
variables.

First, we verify that the potential function is always non-negative.

######  Lemma 3.2.

For any values $x_{i},x^{\textsc{dyn}}_{i}$ of the variables, the potential
function $\phi$ is non-negative.

###### Proof.

Note that $\phi$ only includes variables $x_{i}$ such that
$x^{\textsc{dyn}}_{i}\geq x_{i}$. For such variables,

$\phi_{i}=c_{i}\cdot
x^{\textsc{dyn}}_{i}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{i}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}}=c_{i}\cdot
x^{\textsc{dyn}}_{i}\cdot\ln\frac{1+\delta}{\frac{x_{i}}{x^{\textsc{dyn}}_{i}}+\delta}\geq
0.\qed$

Next, we bound the potential as a function of the variables
$x^{\textsc{dyn}}_{i}$ in the dynamic benchmark:

######  Lemma 3.3.

The potential $\phi_{i}$ for variable $x_{i}$ is at most
$c_{i}x^{\textsc{dyn}}_{i}\cdot\ln\left(1+\frac{1}{\delta}\right)=c_{i}x^{\textsc{dyn}}_{i}\cdot
O(\log k)$. As a consequence, the overall potential $\phi\leq O(\log
k)\cdot\sum_{i=1}^{n}c_{i}x^{\textsc{dyn}}_{i}$.

###### Proof.

We have

$\displaystyle\phi_{i}$
$\displaystyle=c_{i}x^{\textsc{dyn}}_{i}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{i}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}}$ $\displaystyle\leq
c_{i}x^{\textsc{dyn}}_{i}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{i}}{\delta
x^{\textsc{dyn}}_{i}}$
$\displaystyle=c_{i}x^{\textsc{dyn}}_{i}\cdot\ln\left(1+\frac{1}{\delta}\right)$
$\displaystyle=c_{i}x^{\textsc{dyn}}_{i}\cdot O(\log k).\qed$

Finally, we bound the rate of decrease of potential $\phi$ with increase in
the variables $x_{i}$ in Algorithm 1. Our goal is to show that up to constant
factors, the decrease in potential $\phi$ can pay for the increase in cost of
the solution of Algorithm 1.

######  Lemma 3.4.

The rate of decrease of the potential $\phi$ with increase in the variables
$x_{i}$ in Algorithm 1 is at least $\frac{1}{2}$.

###### Proof.

Recall that $\phi_{i}=c_{i}\cdot
x^{\textsc{dyn}}_{i}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{i}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}}$. Therefore,

$\frac{d\phi_{i}}{dx_{i}}=-c_{i}\cdot\frac{x^{\textsc{dyn}}_{i}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}}.$

Recall that in Algorithm 1, the rate of increase of variables $x_{i}$ is given
by $\frac{dx_{i}}{dt}=\frac{a_{ij}}{c_{i}}\left(x_{i}+\delta\cdot
x_{ij}\right)$, where $\delta=\frac{1}{k}$ and
$x_{ij}=\sum_{s=1}^{k}x_{i}(j,s)$. Thus, we have:

$\displaystyle\frac{d\phi_{i}}{dt}=\frac{d\phi_{i}}{dx_{i}}\cdot\frac{dx_{i}}{dt}$
$\displaystyle=-c_{i}\cdot\frac{x^{\textsc{dyn}}_{i}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}}\cdot\frac{a_{ij}}{c_{i}}(x_{i}+\delta\cdot x_{ij})$
$\displaystyle=-a_{ij}\cdot x^{\textsc{dyn}}_{i}\cdot\frac{x_{i}+\delta
x_{ij}}{x_{i}+\delta x^{\textsc{dyn}}_{i}}.$

Now, we have two cases:

  * •

If $x_{ij}\geq x^{\textsc{dyn}}_{i}$, then

$\displaystyle\frac{d\phi_{i}}{dt}=-a_{ij}\cdot
x^{\textsc{dyn}}_{i}\cdot\frac{x_{i}+\delta x_{ij}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}}$ $\displaystyle\leq$ $\displaystyle-a_{ij}\cdot
x^{\textsc{dyn}}_{i}\cdot\frac{x_{i}+\delta x^{\textsc{dyn}}_{i}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}}=-a_{ij}x^{\textsc{dyn}}_{i}.$ (2)

  * •

If $x_{ij}<x^{\textsc{dyn}}_{i}$, then

$\displaystyle\frac{d\phi_{i}}{dt}=-a_{ij}\cdot
x^{\textsc{dyn}}_{i}\cdot\frac{x_{i}+\delta\cdot x_{ij}}{x_{i}+\delta
x^{\textsc{dyn}}_{i}}$ $\displaystyle=$ $\displaystyle-a_{ij}\cdot
x_{ij}\cdot\frac{\frac{x^{\textsc{dyn}}_{i}}{x_{ij}}\cdot x_{i}+\delta\cdot
x^{\textsc{dyn}}_{i}}{x_{i}+\delta x^{\textsc{dyn}}_{i}}<-a_{ij}x_{ij}.$ (3)

We know that at least one of the suggestions in the $j$-th step is supported
by the dynamic benchmark. Let $s(j)\in[k]$ be such a supported suggestion.
Then,

$\displaystyle x_{ij}$ $\displaystyle=\sum_{s=1}^{k}x_{i}(j,s)\geq
x_{i}(j,s(j)),\text{ and }$ $\displaystyle x^{\textsc{dyn}}_{i}$
$\displaystyle\geq x_{i}(j,s(j))\text{ since }s(j)\text{ is supported by
{{dynamic}}}.$

Therefore, in both cases (• ‣ Section 3 and • ‣ Section 3) above, we get

$\frac{d\phi_{i}}{dt}\leq-a_{ij}x_{i}(j,s(j)).$

Let us denote $I_{j}=\\{i\mid x_{i}(j,s(j))\geq x_{i}\\}$. Then, the total
decrease in potential is given by:

$\frac{d\phi}{dt}=\sum_{i:x^{\textsc{dyn}}_{i}\geq
x_{i}}\frac{d\phi_{i}}{dt}\leq-\sum_{i\in I_{j}}a_{ij}x_{i}(j,s(j)).$ (4)

By feasibility of the $s(j)$-th suggestion for the $j$-th constraint, we have
$\sum_{i=1}^{n}a_{ij}x_{i}(j,s(j))\geq 1$. Therefore,

$\displaystyle\sum_{i\in I_{j}}a_{ij}x_{i}(j,s(j))+\sum_{i\notin
I_{j}}a_{ij}x_{i}(j,s(j))$ $\displaystyle\geq 1$ $\displaystyle\text{i.e.,
}\sum_{i\in I_{j}}a_{ij}x_{i}(j,s(j))+\sum_{i\notin I_{j}}a_{ij}x_{i}$
$\displaystyle>1,$

since $x_{i}>x_{i}(j,j(s))$ for $i\notin I_{j}$. Thus,

$\displaystyle\sum_{i\in I_{j}}a_{ij}x_{i}(j,s(j))+\sum_{i}a_{ij}x_{i}$
$\displaystyle>1$ $\displaystyle\text{i.e., }\sum_{i\in
I_{j}}a_{ij}x_{i}(j,s(j))$ $\displaystyle>\frac{1}{2},$

since $\sum_{i=1}^{n}a_{ij}x_{i}<\frac{1}{2}$ in Algorithm 1. The lemma
follows by Equation 4.∎

Theorem 2.1 now follows from the above lemmas using standard arguments as
follows:

###### Proof of Theorem 2.1.

Initially, let $x_{i}=0$ for all $i\in[n]$ but let $x^{\textsc{dyn}}_{i}$ be
their final value. Then, by Lemma 3.3, the potential $\phi$ is at most $O(\log
k)$ times the cost of dynamic. Now, as Algorithm 1 increases the values of the
variables $x_{i}$, it incurs cost at rate at most $\frac{3}{2}$ (by Lemma 3.1)
and the potential $\phi$ decreases at rate at least $\frac{1}{2}$ (by Lemma
3.4). Since $\phi$ is always non-negative (by Lemma 3.2), it follows that the
total cost of the algorithm is at most $3$ times the potential $\phi$ at the
beginning, i.e., at most $O(\log k)$ times the dynamic benchmark. This
completes the proof of Theorem 2.1. ∎

###  3.1 Robust Algorithm for the Online Covering Problem

Now, we prove the robust version of Theorem 2.1, namely Theorem 2.3.

###### Proof of Theorem 2.3.

We run a meta algorithm with two sets of suggestions corresponding to two
solutions. The first solution is obtained by using Algorithm 1 with $k$
suggestions. By Theorem 2.1 this solution has cost at most $O(\log
k)\cdot{\textsc{dynamic}}$. The second solution is produced by the online
algorithm that achieves a competitive ratio of $\alpha$ in the statement of
Theorem 2.3. Using Algorithm 1 again for the meta algorithm, Theorem 2.3 now
follows by invoking Theorem 2.1. ∎

As one particular application of Theorem 2.3, we note that for general ocp,
the best competitive ratio is due to the following result of Gupta and
Nagarajan [GN14] (see also Buchbinder and Naor [BN09b]):

######  Theorem 3.5 (Gupta and Nagarajan [GN14]).

There is an algorithm for the online covering problem that has a competitive
ratio of $O(\log d)$, where $d$ is the maximum number of variables with non-
zero coefficients in any constraint.

This automatically implies the following corollary of Theorem 2.3:

######  Theorem 3.6.

There is an algorithm for the fractional online covering problem that produces
an online solution whose cost is at most $O(\min\\{\log
k\cdot\text{{{dynamic}}},\ln d\cdot{\textsf{opt}}\\})$ in the multiple
predictions setting with $k$ predictions, where $d$ is the maximum number of
non-zero coefficients in any constraints of the online covering problem
instance.

For specific problems that can be modeled as ocp, it might be possible to
obtain a better competitive ratio than $O(\log d)$ by using the structure of
those instances. In that case, the competitive ratio in the multiple
predictions setting also improves accordingly by Theorem 2.3.

###  3.2 Lower Bound for the Online Covering Problem

Here we show that the competitive ratio obtained in Theorem 2.1 is tight,
i.e., we prove Theorem 2.2. We will restrict ourselves to instances of ocp
where $a_{ij}\in\\{0,1\\}$ and $c_{i}=1$ for all $i,j$; this is called the
online (fractional) set cover problem. (We will discuss the set cover problem
in more detail in the next section.) Moreover, our lower bound will hold even
in the experts model, i.e., against the static benchmark. Since the dynamic
benchmark is always at most the static benchmark, it follows that the lower
bound also holds for the dynamic benchmark.

###### Proof of Theorem 2.2.

We index the $k$ experts $\\{1,2\ldots k\\}$ using a uniform random
permutation. We will construct an instance of ocp, where the cost of the
optimal solution is $T$. The instance has $k$ rounds, where in each round
there are $T$ constraints. We index the $j$th constraint of the $i$th round as
$(i,j)$ for $i\in[k],j\in[T]$. There are $kT$ variables that are also indexed
as $(i,j)$ for $i\in[k],j\in[T]$. Constraint $(i,j)$ is satisfied by each of
the variables $(i^{\prime},j)$ for all $i^{\prime}\geq i$ (i.e.,
$a_{(i,j),(i^{\prime},j)}=1$). When constraint $(i,j)$ is presented (in round
$i$), expert $i^{\prime}$ for every $i^{\prime}\geq i$ sets variable
$(i^{\prime},j)$ to $1$ to satisfy it. (The suggestions of experts
$i^{\prime\prime}<i$ are immaterial in this round, and they can set any
arbitrary variable satisfying constraint $(i,j)$ to $1$.)

The optimal solution is to follow expert $k$, i.e., the variables $(k,j)$ for
all $j\in[T]$ should be set to $1$; this has cost $T$. After round $i$, the
cumulative expected cost of any deterministic algorithm across the variables
$(i,1),(i,2),\ldots,(i,T)$ is at least $\frac{T}{i}$. Across all $i\in[k]$,
this adds up to a total expected cost
$T\cdot\left(1+\frac{1}{2}+\ldots+\frac{1}{k}\right)=\Omega(T\log k)$. The
theorem then follows by Yao’s minimax principle [Yao77]. ∎

##  4 Online Set Cover

In the (weighted) set cover problem, we are given a collection of subsets
$\cal S$ of a ground set $U$, where set $S\in{\cal S}$ has weight $w_{S}$. The
goal is to select a collection of sets ${\cal T}\subseteq{\cal S}$ of minimum
cost $\sum_{T\in{\cal T}}w_{T}$ that cover all the elements in $U$, i.e., that
satisfies $\cup_{T\in{\cal T}}T=U$. In the online version of this problem (see
[AAA+09]), the set of elements in $U$ is not known in advance. In each online
step, a new element $u\in U$ is revealed, and the sets in $\cal S$ that
contain $u$ are identified. If $u$ is not covered by the sets in the current
solution $\cal T$, then the algorithm must augment $\cal T$ by adding some set
containing $u$ to it.

In the fractional version of the set cover problem, sets can be selected to
fractions in $[0,1]$, i.e., a solution is given by variables $x_{S}\in[0,1]$
for all $S\in{\cal S}$. The constraint is that the total fraction of all sets
containing each element $u$ must be at least $1$, i.e., $\sum_{S:u\in
S}x_{S}\geq 1$ for every element $u\in U$. The cost of the solution is given
by $\sum_{S\in{\cal S}}w_{S}x_{S}$. Clearly, this is a special case of the
online covering problem in the previous section where each variable $x_{i}$
represents a set and each constraint $\sum_{i=1}^{n}a_{ij}x_{i}\geq 1$ is for
an element, where $a_{ij}=1$ if an only if element $j$ is in set $i$, else
$a_{ij}=0$.

We define the frequency of an element to be the number of sets containing it,
and denote the maximum frequency of any element by $d$. Note that this
coincides with the maximum number of non-zero coefficients in any constraint.
The following theorem is an immediate corollary of Theorem 3.6:

######  Theorem 4.1.

There is an algorithm for the fractional online set cover problem that
produces an online solution whose cost is at most $O(\min\\{\ln
k\cdot\text{{{dynamic}}},\ln d\cdot{\textsf{opt}}\\})$ in the multiple
predictions setting with $k$ predictions.

It is interesting to note that when the suggestions are good in the sense that
${\textsc{dynamic}}=O({\textsf{opt}})$, the competitive ratio of $O(\log k)$
in the above theorem is independent of the size of the problem instance. In
contrast, for the classical fractional online set cover problem, there is a
well-known lower bound of $\Omega(\log d)$ on the competitive ratio. We also
note that the competitive ratio in Theorem 4.1 is tight since as we noted
earlier, the lower bound instance constructed in Theorem 2.2 is actually an
instance of the set cover problem.

###  4.1 Online Rounding and the Integral Set Cover Problem

Next, we consider the integral set cover problem, i.e., where the variables
$x_{i}$ are required to be integral, i.e., in $\\{0,1\\}$ rather than in
$[0,1]$. The following a well-known result on rounding fractional set cover
solutions online:

######  Theorem 4.2 (Alon et al. [AAA+09]).

Given any feasible solution to the fractional online set cover problem, there
is an online algorithm for finding a feasible solution to the integral online
set cover problem whose cost is at most $O(\log m)$ times that of the
fractional solution, where $m$ is the number of elements.

By applying this theorem on the fractional solution produced by Theorem 4.1,
we get a competitive ratio of $O(\log m\log k)$ for the integral online set
cover problem with $k$ predictions against the dynamic benchmark:

######  Theorem 4.3.

There is an algorithm for the integral online set cover problem that produces
an online solution whose cost is at most $O(\min\\{\ln m\ln
k\cdot\text{{{dynamic}}},\ln m\ln d\cdot{\textsf{opt}}\\})$ in the multiple
predictions setting with $k$ predictions.

It is well-known that the competitive ratio of the integral online set cover
problem (without predictions) is at least $\tilde{\Omega}(\log m\log d)$
[AAA+09]333The notation $\tilde{\Omega}$ (and $\tilde{O}$) hide lower order
terms.. In the degenerate case of $k=d$, any instance of online set cover can
be generated in the $k$ predictions settings where the benchmark solution
dynamic will be the optimal solution, since all the sets containing an element
can be provided as suggestions in each online step. As a consequence, the
competitive ratio in Theorem 4.3 is tight (up to lower order terms).

##  5 (Weighted) Caching

The caching problem is among the most well-studied online problems (see, e.g.,
[ST85, FKL+91, MS91, ACN00, You91, BBK99], and the textbook [BEY98]). In this
problem, there is a set of $n$ pages and a cache that can hold any $h$ pages
at a time.444The usual notation for cache size is $k$, but we have changed it
to $h$ since we are using $k$ to denote the number of suggestions. In every
online step $j$, a page $p_{j}$ is requested; if this page is not in the
cache, then it has to be brought into the cache (called fetching) by evicting
an existing page from the cache. In the weighted version (see, e.g., [CKPV91,
You94, BBN07]), the cost of fetching a page $p$ into the cache is given by its
non-negative weight $w_{p}$. (In the unweighted version, $w_{p}=1$ for all
pages.) The goal of a caching algorithm is to minimize the total cost of
fetching pages while serving all requests.

The (weighted) caching problem can be formulated as online covering problem by
defining variables $x_{p}(r)\in\\{0,1\\}$ to indicate whether page $p$ is
evicted between its $r$-th and $(r+1)$-st requests. Let $r(p,j)$ denote the
number of times page $p$ is requested until (and including) the $j$-th
request. For any online step $j$, let $B(j)=\\{p:r(p,j)\geq 1\\}$ denote the
set of pages that have been requested until (and including) the $j$-th
request. The covering program formulation is as follows:

$\begin{array}[]{ll@{}ll}\text{min}&\sum_{p}\sum_{r}w_{p}\cdot x_{p}(r)\text{
subject to}&\\\ &\sum_{p\in B(j),p\neq
p_{j}}x_{p}(r(p,j))\geq|B(j)|-h,&~{}\forall j\geq 1\\\
&x_{p}(r)\in\\{0,1\\},&\forall p,\forall r\geq 1\\\ \end{array}$

In the fractional version of the problem, we replace the constraints
$x_{p}(r)\in\\{0,1\\}$ with the constraints $x_{p}(r)\in[0,1]$. Clearly, this
fits the definition of the online covering problem.555Strictly speaking, we
need to scale the first set of coefficients by $|B(j)|-h$, but as we mentioned
earlier, this is equivalent since scaling the coefficients has no bearing on
the competitive ratio of our algorithm. Moreover, for the fractional weighted
caching problem, Bansal, Buchbinder, and Naor gave an online algorithm with a
competitive ratio of $O(\log h)$:

######  Theorem 5.1 ([BBN07]).

There is an online algorithm for the fractional weighted caching problem with
a competitive ratio of $O(\log h)$.

Note that the competitive ratio of $O(\log h)$ is better than that given by
Theorem 3.5 since the cache size $h$ is typically much smaller than the total
number of pages. Now, we apply Theorem 2.3 to get the following result for
fractional weighted caching with $k$ predictions:

######  Theorem 5.2.

There is an algorithm for the fractional weighted caching problem that
produces an online solution whose cost is at most $O(\min\\{\ln
k\cdot\text{{{dynamic}}},\ln h\cdot{\textsf{opt}}\\})$ in the multiple
predictions setting with $k$ predictions.

###  5.1 Integral (Weighted) Caching

Next, we consider the integral weighted caching problem, i.e., where the
variables $x_{p}(r)$ have to be in $\\{0,1\\}$ rather than $[0,1]$. We use the
following known result about online rounding of fractional weighted caching
solutions:

######  Theorem 5.3 (Bansal, Buchbinder, and Naor [BBN07]).

Given any feasible online solution to the fractional weighted caching problem,
there is an online algorithm for finding a feasible online solution to the
integral weighted caching problem whose cost is at most $O(1)$ times that of
the fractional solution.

By applying this theorem on the fractional solution produced by Theorem 5.2,
we get a competitive ratio of $O(\log k)$ for the integral weighted caching
problem with $k$ predictions against the dynamic benchmark:

######  Theorem 5.4.

There is an online algorithm for the integral weighted caching problem that
produces an online solution whose cost is at most $O(\min\\{\ln
k\cdot\text{{{dynamic}}},\ln h\cdot{\textsf{opt}}\\})$ in the multiple
predictions setting with $k$ predictions.

##  6 Online Covering with Box Constraints

In this section, we generalize the online covering framework in Section 2 by
allowing additional box constraints of the form $x_{ij}\leq y_{i}$. The new
linear program is given by:

$\displaystyle\text{Minimize }\sum_{i=1}^{n}c_{i}y_{i}$
$\displaystyle+\sum_{i=1}^{n}\sum_{j=1}^{m}d_{ij}x_{ij}\text{ subject to}$
$\displaystyle x_{ij}$ $\displaystyle\leq y_{i}\quad\forall i,j$ (5)
$\displaystyle\sum_{i=1}^{n}a_{ij}x_{ij}$ $\displaystyle=1\quad\forall j$ (6)
$\displaystyle y_{i}$ $\displaystyle\in[0,1]\quad\forall i$ (7)

The box constraints $x_{ij}\leq y_{i}$ do not have coefficients and hence are
known offline. As in ocp, the cost coefficients $c_{i}$ are known offline. In
each online step, a new covering constraint $\sum_{i=1}^{n}a_{ij}x_{ij}\geq 1$
is revealed to the algorithm, and the corresponding cost coefficient $d_{ij}$
is also revealed.

We first note that this is a generalization of the online covering problem. To
see this, set $d_{ij}=0$. Then, we get:

$\min_{y_{i}\in[0,1]:i\in[n]}\left\\{\sum_{i=1}^{n}c_{i}y_{i}:\sum_{i=1}^{n}a_{ij}y_{i}\geq
1~{}\forall j\in[m]\right\\},$

which is precisely the online covering problem.

The more general version captures problems like facility location (shown in
the next section) that are not directly modeled by ocp. We denote the $s$-th
suggestion for the $j$-th constraint by variables $y_{i}(j,s)$ and
$x_{ij}(s)$; they satisfy $\sum_{i=1}^{n}a_{ij}x_{ij}(s)\geq 1$, i.e., all
suggestions are feasible.

###  6.1 Online Algorithm

Our algorithm for ocp with box constraints is given in Algorithm 2. As
earlier, for all $i$, we simultaneously raise $x_{ij}$ (and possibly $y_{i}$
as well) at the rate specified by the algorithm. As in the case of ocp, we
raise these variables only till the constraint is satisfied up to a factor of
$\frac{1}{2}$, and any individual variable does not cross $\frac{1}{2}$. This
allows us to double all variable and satisfy the constraints at an additional
factor of $2$ in the cost. Moreover, the same argument as in Algorithm 1
implies that this algorithm is also feasible, i.e., there is at least one
variable that can be increased in the while loop.

0.1 On arrival of a new constraint $\sum_{i=1}^{n}a_{ij}x_{ij}=1$:

0.2 Initialize $x_{ij}=0,\quad\forall j$.

0.3 Set $\Gamma_{ij}:=\sum_{s=1}^{k}x_{ij}(s),\quad\forall j$ and
$\delta=\frac{1}{k}$.

0.4 while $\sum_{j}x_{ij}<\frac{1}{2}$

0.5 for all $i$ such that $x_{ij}<\frac{1}{2}$:

0.6 if $x_{ij}<y_{i}$

0.7 Increase $x_{ij}$ at the rate $\frac{\partial x_{ij}}{\partial
t}=\left(\frac{a_{ij}}{d_{ij}}\right)\cdot\left(x_{ij}+\delta\cdot\Gamma_{ij}\right)$

0.8 else

0.9 Increase both variables $x_{ij},y_{i}$ at the same rate

0.10 $\frac{\partial y_{i}}{\partial t}=\frac{\partial x_{ij}}{\partial
t}=\left(\frac{a_{ij}}{d_{ij}+c_{i}}\right)\cdot\left(x_{ij}+\delta\cdot\Gamma_{ij}\right)$.

Algorithm 2 Algorithm for Online Facility Location

###  6.2 Analysis

In this section, we analyze Algorithm 2. We first bound the rate of increase
of the cost of the algorithm.

######  Lemma 6.1.

The rate of increase of the cost for Algorithm 2 is at most $\frac{3}{2}$.

###### Proof.

Consider Algorithm 2 when the constraint $\sum_{i=1}^{n}a_{ij}x_{ij}=1$
arrives. For any $i$, we claim:

$\displaystyle d_{ij}\cdot\frac{\partial x_{ij}}{\partial
t}+c_{i}\cdot\frac{\partial y_{i}}{\partial
t}=a_{ij}\left(x_{ij}+\delta\cdot\Gamma_{ij}\right).$ (8)

To show this, there are two cases to consider:

  * •

$x_{ij}<y_{i}$: In this case, $\frac{\partial y_{i}}{\partial t}=0$, and
$d_{ij}\cdot\frac{\partial x_{ij}}{\partial
t}=a_{ij}\left(x_{ij}+\delta\cdot\Gamma_{ij}\right)$ and so (8) holds.

  * •

$x_{ij}=y_{i}$: In this case, $\frac{\partial y_{i}}{\partial
t}=\frac{\partial x_{ij}}{\partial
t}=\frac{a_{ij}}{d_{ij}+c_{i}}\cdot\left(x_{ij}+\frac{\Gamma_{ij}}{k}\right)$,
i.e., $c_{i}\cdot\frac{\partial y_{i}}{\partial t}+d_{ij}\cdot\frac{\partial
x_{ij}}{\partial t}=a_{ij}\left(x_{ij}+\delta\cdot\Gamma_{ij}\right)$, and so
(8) holds.

Therefore, the rate of change of the objective function is given by:

$\sum_{i}\left(d_{ij}\cdot\frac{\partial x_{ij}}{\partial
t}+c_{i}\cdot\frac{\partial y_{i}}{\partial
t}\right)\stackrel{{\scriptstyle\eqref{eq:proof1}}}{{=}}\sum_{i}a_{ij}\left(x_{ij}+\delta\cdot\Gamma_{ij}\right)=\sum_{i}a_{ij}x_{ij}+\frac{\sum_{s}\sum_{i}a_{ij}x_{ij}(s)}{k}\leq\frac{1}{2}+1=\frac{3}{2}.\qed$

We now describe the potential function, which has a similar structure as that
in the online covering framework. Let
$x^{\textsc{dyn}}_{ij},y^{\textsc{dyn}}_{i}$ denote the values of the
variables $x_{ij},y_{i}$ respectively in the benchmark solution dynamic. The
potential function for a variable $x_{ij}$ is then defined as follows:

$\phi_{ij}=d_{ij}\cdot
x^{\textsc{dyn}}_{ij}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}},\text{ where }\delta=\frac{1}{k},$

and the potential for the variable $y_{i}$ is given by

$\psi_{i}=c_{i}\cdot
y^{\textsc{dyn}}_{i}\cdot\ln\frac{(1+\delta)y^{\textsc{dyn}}_{i}}{y_{i}+\delta
y^{\textsc{dyn}}_{i}}.$

As before, the overall potential is

$\phi=\sum_{i,j:x^{\textsc{dyn}}_{ij}\geq
x_{ij}}\phi_{ij}+\sum_{i:y^{\textsc{dyn}}_{i}\geq y_{i}}\psi_{i}.$

The rest of the proof proceeds along the same lines as that for the online
covering problem. But we give the details for the sake of completeness.

The next lemma is the analogue of Lemma 3.2, and shows that the potential
$\phi$ is always non-negative.

######  Lemma 6.2.

For any values of the variables
$x_{ij},y_{i},x^{\textsc{dyn}}_{ij},y^{\textsc{dyn}}_{i}$, the potential
function $\phi$ is non-negative.

###### Proof.

We show that each of the quantities $\phi_{ij},\psi_{i}$ in the expression for
$\phi$ is non-negative. Consider a pair $i,j$ for which
$x^{\textsc{dyn}}_{ij}\geq x_{ij}$. Then

$\phi_{ij}=d_{ij}\cdot
x^{\textsc{dyn}}_{ij}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}}=d_{ij}\cdot
x^{\textsc{dyn}}_{ij}\cdot\ln\frac{1+\delta}{\frac{x_{ij}}{x^{\textsc{dyn}}_{ij}}+\delta}\geq
0.$

Similarly, $\psi_{i}\geq 0$ if $y^{\textsc{dyn}}_{i}\geq y_{i}$. This shows
that $\phi\geq 0$. ∎

Now we bound the potential against the benchmark solution dynamic. The proof
of this lemma is very similar to that of Lemma 3.3.

######  Lemma 6.3.

The following bounds hold: $\phi_{ij}\leq d_{ij}\cdot
x^{\textsc{dyn}}_{ij}\cdot\ln(1+\frac{1}{\delta})=d_{ij}x^{\textsc{dyn}}_{ij}\cdot
O(\log k)$ and $\psi_{i}\leq c_{i}\cdot
y^{\textsc{dyn}}_{i}\cdot\ln(1+\frac{1}{\delta}))=c_{i}y^{\textsc{dyn}}_{i}\cdot
O(\log k)$. As a consequence, the overall potential $\phi\leq O(\log
k)\cdot\left(\sum_{i}\sum_{j}d_{ij}x^{\textsc{dyn}}_{ij}+\sum_{j}c_{i}y^{\textsc{dyn}}_{i}\right)$.

###### Proof.

We have

$\phi_{ij}=d_{ij}x^{\textsc{dyn}}_{ij}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{ij}}{x_{i}+\delta
x^{\textsc{dyn}}_{ij}}\leq
d_{ij}x^{\textsc{dyn}}_{ij}\cdot\ln\frac{(1+\delta)x^{\textsc{dyn}}_{ij}}{\delta
x^{\textsc{dyn}}_{ij}}=d_{ij}x^{\textsc{dyn}}_{ij}\cdot\ln\left(1+\frac{1}{\delta}\right)=d_{ij}x^{\textsc{dyn}}_{ij}\cdot
O(\log k).$

The bound for $\psi_{i}$ also follows similarly. ∎

Finally, we bound the rate of decrease of potential $\phi$ with increase in
the variables in Algorithm 2.

######  Lemma 6.4.

The rate of decrease of the potential $\phi$ in Algorithm 2 is at least
$\frac{1}{2}$.

###### Proof.

It is easy to check that

$\frac{\partial\phi_{ij}}{\partial
x_{ij}}=-\frac{d_{ij}x^{\textsc{dyn}}_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}},\quad\frac{\partial\psi_{i}}{\partial
y_{i}}=-\frac{c_{i}y^{\textsc{dyn}}_{i}}{y_{i}+\delta y^{\textsc{dyn}}_{i}}.$
(9)

Consider the step when the $j$-th constraint arrives. We claim that for any
index $i\in[n]$,

$\displaystyle\frac{\partial\left(\phi_{ij}+\psi_{i}\right)}{\partial t}\leq-
a_{ij}x^{\textsc{dyn}}_{ij}\cdot\frac{x_{ij}+\delta\Gamma_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}}.$ (10)

To prove this, we consider two cases:

  * •

$x_{ij}<y_{i}$: In this case, $\frac{\partial x_{ij}}{\partial
t}=\frac{a_{ij}}{d_{ij}}\cdot\left(x_{ij}+\delta\Gamma_{ij}\right),\frac{\partial
y_{i}}{\partial t}=0$. Combining this with (9), we see that

$\frac{\partial\left(\phi_{ij}+\psi_{i}\right)}{\partial
t}=\frac{\partial\phi_{ij}}{\partial t}=\frac{\partial\phi_{ij}}{\partial
x_{ij}}\cdot\frac{\partial x_{ij}}{\partial
t}=-a_{ij}x^{\textsc{dyn}}_{ij}\cdot\frac{x_{ij}+\delta\Gamma_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}}.$

  * •

$x_{ij}=y_{i}$: In this case, $\frac{\partial x_{ij}}{\partial
t}=\frac{\partial y_{i}}{\partial
t}=\frac{a_{ij}}{d_{ij}+c_{i}}\cdot\left(x_{ij}+\frac{\Gamma_{ij}}{k}\right).$
Using (9) again and the fact that $y_{i}=x_{ij}$, we see that

$\frac{\partial\left(\phi_{ij}+\psi_{i}\right)}{\partial
t}=\frac{\partial\phi_{ij}}{\partial x_{ij}}\cdot\frac{\partial
x_{ij}}{\partial t}+\frac{\partial\psi_{i}}{\partial y_{i}}\cdot\frac{\partial
y_{i}}{\partial
t}=-\frac{a_{ij}}{c_{i}+d_{ij}}\left(\frac{d_{ij}x^{\textsc{dyn}}_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}}+\frac{c_{i}y^{\textsc{dyn}}_{i}}{x_{ij}+\delta
y^{\textsc{dyn}}_{i}}\right)\cdot\left(x_{ij}+\delta\Gamma_{ij}\right).$

Since $y^{\textsc{dyn}}_{i}\geq
x^{\textsc{dyn}}_{ij},\frac{y^{\textsc{dyn}}_{i}}{x_{ij}+\delta
y^{\textsc{dyn}}_{i}}\geq\frac{x^{\textsc{dyn}}_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}}.$ Therefore, the RHS above is at most
$-a_{ij}x^{\textsc{dyn}}_{ij}\cdot\frac{x_{ij}+\delta\Gamma_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}}.$

Thus, we have shown that inequality (10) always holds. Now, we have two cases:

  * •

$\Gamma_{ij}\geq x^{\textsc{dyn}}_{ij}$: Inequality (10) implies that

$\frac{\partial(\phi_{ij}+\psi_{i})}{\partial t}\leq-
a_{ij}x^{\textsc{dyn}}_{ij}.$

  * •

$\Gamma_{ij}<x^{\textsc{dyn}}_{ij}$: Using (10) again, we see that

$\frac{d(\phi_{ij}+\psi_{i})}{dt}\leq-
a_{ij}x^{\textsc{dyn}}_{ij}\cdot\frac{x_{ij}+\delta\cdot\Gamma_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}}=-a_{ij}\Gamma_{ij}\cdot\frac{\frac{x^{\textsc{dyn}}_{ij}}{\Gamma_{ij}}\cdot
x_{ij}+\delta\cdot x^{\textsc{dyn}}_{ij}}{x_{ij}+\delta
x^{\textsc{dyn}}_{ij}}\leq-a_{ij}\Gamma_{ij}.$

We know that at least one of the suggestions in the $i$-th step is supported
by the dynamic benchmark. Let $s(j)\in[k]$ be the index of such a supported
suggestion. Then,

$\displaystyle\Gamma_{ij}$ $\displaystyle=\sum_{s=1}^{k}x_{ij}(s)\geq
x_{ij}(s(j)),\text{ and }$ $\displaystyle x^{\textsc{dyn}}_{ij}$
$\displaystyle\geq x_{ij}(s(j))\text{ since }s(j)\text{ is supported by
{{dynamic}}}.$

Therefore, in both cases above, we get

$\frac{\partial(\phi_{ij}+\psi_{i})}{\partial t}\leq-a_{ij}\cdot
x_{ij}(s(j)).$

Let $I$ denote the index set $\\{i\in[n]:x^{\textsc{dyn}}_{ij}\geq x_{ij}\\}$
(here $j$ is fixed). We claim that the total decrease in potential satisfies:

$\displaystyle\frac{\partial\phi}{\partial t}\leq-\sum_{i\in I}a_{ij}\cdot
x_{ij}(s(j)).$ (11)

To see this, let $I^{\prime}$ denote the index set
$\\{i:y^{\textsc{dyn}}_{i}\geq y_{i}\\}$. Then the term in $\phi$
corresponding to step $j$ is $\phi_{j}:=\sum_{i\in I}\phi_{ij}+\sum_{i\in
I^{\prime}}\psi_{i}.$ First consider an index $i\in I$ for which
$x_{ij}<y_{i}$. In this case, we know that $\frac{\partial\psi_{i}}{\partial
t}=0$, and so irrespective of whether $i$ belongs to $I^{\prime}$ or not, the
rate of change of the terms in $\phi_{j}$ corresponding to $i$ is

$\frac{\partial(\phi_{ij}+\psi_{i})}{\partial t}\leq-a_{ij}\cdot
x_{ij}(s(j)).$

Now consider an index $i\in I$ for which $x_{ij}=y_{i}$. Since
$y^{\textsc{dyn}}_{i}\geq x^{\textsc{dyn}}_{ij}$, it follows that
$y^{\textsc{dyn}}_{i}\geq y_{i}$ and so $i\in I^{\prime}$ as well. Therefore,
the rate of change of the terms in $\phi_{j}$ corresponding to $i$ is equal to

$\frac{\partial(\phi_{ij}+\psi_{i})}{\partial t}\leq-a_{ij}\cdot
x_{ij}(s(j)).$

Finally, consider an index $i\in I^{\prime}\setminus I$. It is easy to verify
that $\frac{\partial\psi_{i}}{\partial t}\leq 0$. Thus, inequality (11)
follows.

The rest of the argument proceeds as in the proof of Lemma 3.4. By feasibility
of the $s(j)$-th suggestion in step $j$, we have:

$\displaystyle\sum_{j}a_{ij}x_{ij}(s(j))$ $\displaystyle\geq 1$
$\displaystyle\text{i.e., }\sum_{i\in I}a_{ij}x_{ij}(s(j))+\sum_{i\notin
I}a_{ij}x_{ij}(s(j))$ $\displaystyle\geq 1$ $\displaystyle\text{i.e.,
}\sum_{i\in I}a_{ij}x_{ij}(s(j))+\sum_{i\notin I}a_{ij}x_{ij}$
$\displaystyle>1\quad\quad\left(\text{since }i\notin I,\text{ we have
}x_{ij}>x^{\textsc{dyn}}_{ij}\geq x_{ij}(s(j))\right)$
$\displaystyle\text{i.e., }\sum_{i\in
I}a_{ij}x_{ij}(s(j))+\sum_{i=1}^{n}a_{ij}x_{ij}$ $\displaystyle>1$
$\displaystyle\text{i.e., }\sum_{i\in I}a_{ij}x_{ij}(s(j))$
$\displaystyle>\frac{1}{2}\quad\left(\text{since
}\sum_{i=1}^{n}x_{ij}<\frac{1}{2}\text{ in \lx@cref{creftypecap~refnum}{alg:
Dynamic_OPT_fac_loc}}\right).$

The desired result now follows from (11). ∎

We now combine these lemmas to show the following result:

######  Theorem 6.5.

There is an algorithm for the online covering problem with box constraints
that produces an online solution whose cost is at most $O(\log
k)\cdot{\textsc{dynamic}}$ in the multiple predictions setting with $k$
predictions.

###### Proof.

Initially, let $x_{ij}=y_{i}=0$ for all $i,j$ but let
$x^{\textsc{dyn}}_{ij},y^{\textsc{dyn}}_{i}$ be their final value. Then, by
Lemma 6.3, the potential $\phi$ is at most $O(\log k)$ times the cost of
dynamic. Now, as Algorithm 2 increases the values of the variables
$x_{ij},y_{i}$, it incurs cost at rate at most $\frac{3}{2}$ (by Lemma 6.1)
and the potential $\phi$ decreases at rate at least $\frac{1}{2}$ (by Lemma
6.4). Since $\phi$ is always non-negative (by Lemma 6.2), it follows that the
total cost of the algorithm is at most $3$ times the potential $\phi$ at the
beginning, i.e., at most $O(\log k)$ times the dynamic benchmark. ∎

We can also robustify the solution produced by Algorithm 2 using the same
ideas as in Theorem 2.3. Namely, we run Algorithm 2 to produce one solution
and an online algoeithm without prediction to obtain another solution. Then,
these two solutions are fed into a meta algorithm running Algorithm 2 to
obtain the final solution. We get the following analog of Theorem 2.3:

######  Theorem 6.6.

Suppose a class of online covering problems with box constraints have an
online algorithm (without predictions) whose competitive ratio is $\alpha$.
Then, there is an algorithm for this class of online covering problems with
box constraint with $k$ suggestions that produces an online solution whose
cost is at most $O(\min\\{\ln
k\cdot\text{{{dynamic}}},\alpha\cdot{\textsf{opt}}\\})$.

##  7 Online Facility Location

We now apply the online covering with box constraints framework to the online
Facility Location problem. We first describe the offline version of this
problem. An instance of the Facility Location is given by a metric space
$d(\cdot,\cdot)$, a set of $n$ potential facility location points $\cal F$,
and a set $\cal R$ of clients in the metric space. Further, each location
$f_{i}\in{\cal F}$ has a facility opening cost $o_{i}$. A solution opens a
subset ${\cal F}^{\prime}\subseteq{\cal F}$ of facilities, and assigns each
client $r_{j}$ to the closest open facility $f_{i_{j}}\in{\cal F}^{\prime}$.
The connection cost of this client is $d(r_{j},f_{i_{j}})$ and the goal is to
minimize the sum of the connection costs of all the clients and the facility
opening costs of the facilities in ${\cal F}^{\prime}.$

In the online Facility Location problem, clients arrive over time and the
solution needs to assign each arriving client to an open facility. The
algorithm can also open facilities at any time. This problem was first studied
by Meyerson [Mey01] who gave a competitive ratio of $O(\log n)$ for $n$
clients. This was later improved (and derandomized) by Fotakis [Fot08] to
$O(\frac{\log n}{\log\log n})$. Since then, many variants of the problem have
been studied; for a survey of the results, the reader is referred to [Fot11].

We now describe the natural LP relaxation for Facility Location; our notion of
a fractional solution will be with respect to this LP relaxation. We have
variables $y_{i}$ for each facility location $f_{i}\in{\cal F}$, which denotes
the extent to which facility $f_{i}$ is open, and variables $x_{ij}$ for each
client $r_{j}$ and facility $f_{i}$ denoting the extent to which $r_{j}$ is
assigned to $f_{i}$. The relaxation is as follows:

$\displaystyle\text{Minimize }\sum_{i=1}^{m}o_{i}y_{i}$
$\displaystyle+\sum_{i=1}^{n}\sum_{j=1}^{m}d_{ij}x_{ij}\text{ subject to}$
$\displaystyle x_{ij}$ $\displaystyle\leq y_{i}\quad\forall i,j$
$\displaystyle\sum_{i=1}^{n}x_{ij}$ $\displaystyle=1\quad\forall i$
$\displaystyle y_{i}$ $\displaystyle\in[0,1]\quad\forall j$

Notice that this is a special case of the online covering problem with box
constraints, where $c_{i}=o_{i}$ for all $i$, and $a_{ij}=1$ for all $i,j$.
Thus, we can apply Algorithm 2 for online Facility Location problem as well.
Moreover, as mentioned earlier, there is an algorithm (due to Fotakis [Fot08])
for the online facility location problem (without predictions) that has a
competitive ratio of at most $O(\log n)$ for $n$ clients. As a corollary of
Theorem 6.6, we get the following result:

######  Theorem 7.1.

There is an algorithm for the fractional online Facility Location problem that
produces an online solution whose cost is at most $O(\min\left\\{\frac{\ln
n}{\ln\ln n}\cdot{\textsf{opt}},\ln k\cdot{\textsc{dynamic}}\right\\})$ in the
multiple predictions setting with $k$ predictions.

We also note that the $O(\log k)$ bound in Theorem 7.1 cannot be improved
further (except lower order terms). This is because we can simulate an
instance of the online facility location problem without predictions by giving
all prior client locations as suggested facility locations for $k=n$.
Furthermore, a lower bound of $\Omega\left(\frac{\log n}{\log\log n}\right)$
is also known (due to Fotakis [Fot08]) for online facility location, and this
lower bound construction easily extends to the fractional version of the
problem.

##  8 Future Directions

This paper presented a general recipe for the design of online algorithms with
multiple machine-learned predictions. This general technique was employed to
obtain tight results for classical online problems such as set cover,
(weighted) caching, and facility location. We believe this framework can be
applied to other online covering problems as well. In particular, it would be
interesting to consider the $k$-server problem with multiple suggestions in
each step specifying the server that should serve the new request. It would
also be interesting to extend this framework to some packing problems such as
online budgeted allocation, and to more general settings for mixed packing and
covering linear programs and non-linear (convex) objectives. From a technical
standpoint, our potential-based analysis introduces several new ideas that can
be useful even in the competitive analysis of classical online algorithms.

## References

  * [AAA+06] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor.  A general approach to online network optimization problems.  ACM Transactions on Algorithms, 2(4):640–660, 2006.
  * [AAA+09] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor.  The online set cover problem.  SIAM J. Comput., 39(2):361–370, 2009.
  * [ABC+16] Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, and Debmalya Panigrahi.  Online algorithms for covering and packing problems with convex objectives.  In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 148–157, 2016.
  * [ABFP13] Yossi Azar, Umang Bhaskar, Lisa Fleischer, and Debmalya Panigrahi.  Online mixed packing and covering.  In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 85–100. SIAM, 2013.
  * [ACE+20] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  In Proceedings of the 37th International Conference on Machine Learning,ICML 2020, 2020.
  * [ACL+21] Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re.  Online facility location with multiple advice.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, 2021\.
  * [ACN00] Dimitris Achlioptas, Marek Chrobak, and John Noga.  Competitive analysis of randomized paging algorithms.  Theor. Comput. Sci., 234(1-2):203–218, 2000.
  * [AGKK20] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  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, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [AGKP21] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi.  A regression approach to learning-augmented online algorithms.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021., 2021\.
  * [AGP20] 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.
  * [ALT21] 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 Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1070–1080. ACM, 2021.
  * [APT22] Yossi Azar, Debmalya Panigrahi, and Noam Touitou.  Online graph algorithms with predictions.  In Proceedings of the Thirty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, January 9-12, 2022.
  * [BBK99] Avrim Blum, Carl Burch, and Adam Kalai.  Finely-competitive paging.  In 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA, pages 450–458. IEEE Computer Society, 1999.
  * [BBN07] Nikhil Bansal, Niv Buchbinder, and Joseph Naor.  A primal-dual randomized algorithm for weighted paging.  In FOCS, pages 507–517, 2007.
  * [BBN10] Nikhil Bansal, Niv Buchbinder, and Joseph Seffi Naor.  A simple analysis for randomized online weighted paging.  Unpublished Manuscript, 2010.
  * [BC21] Nikhil Bansal and Christian Coester.  Online metric allocation.  CoRR, abs/2111.15169, 2021.
  * [BCK+20] Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee.  Scale-free allocation, amortized convexity, and myopic weighted paging.  CoRR, abs/2011.09076, 2020.
  * [BCKP20] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit.  Online linear optimization with many hints.  Advances in neural information processing systems, 33:9530–9539, 2020.
  * [BEY98] A. Borodin and R. El-Yaniv.  Online Computation and Competitive Analysis.  Cambridge University Press, 1998.
  * [BGMN19] Niv Buchbinder, Anupam Gupta, Marco Molinaro, and Joseph (Seffi) Naor.  k-servers with a smile: Online algorithms via projections.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 98–116. SIAM, 2019.
  * [BJN07] Niv Buchbinder, Kamal Jain, and Joseph Naor.  Online primal-dual algorithms for maximizing ad-auctions revenue.  In ESA, pages 253–264, 2007.
  * [BMRS20] É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, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [BMS20] Étienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  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, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [BN09a] Niv Buchbinder and Joseph Naor.  The design of competitive online algorithms via a primal-dual approach.  Foundations and Trends in Theoretical Computer Science, 3(2-3):93–263, 2009.
  * [BN09b] Niv Buchbinder and Joseph Naor.  Online primal-dual algorithms for covering and packing.  Math. Oper. Res., 34(2):270–286, 2009.
  * [CKPV91] Marek Chrobak, H Karloof, Tom Payne, and S Vishwnathan.  New results on server problems.  SIAM Journal on Discrete Mathematics, 4(2):172–181, 1991.
  * [DLLV21] 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 409–429. ACM, 2021\.
  * [EIN+21] Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner.  Learning-based support estimation in sublinear time.  In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
  * [FGGP21] Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris.  Learning augmented online facility location.  CoRR, abs/2107.08277, 2021.
  * [FKL+91] Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young.  Competitive paging algorithms.  J. Algorithms, 12(4):685–699, 1991.
  * [Fot08] Dimitris Fotakis.  On the competitive ratio for online facility location.  Algorithmica, 50(1):1–57, 2008.
  * [Fot11] Dimitris Fotakis.  Online and incremental algorithms for facility location.  SIGACT News, 42(1):97–131, 2011.
  * [GN14] Anupam Gupta and Viswanath Nagarajan.  Approximating sparse covering integer programs online.  Math. Oper. Res., 39(4):998–1011, 2014.
  * [GP19] 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.
  * [HIKV19] Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian.  Learning-based frequency estimation algorithms.  In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
  * [IVY19] Piotr Indyk, Ali Vakilian, and Yang Yuan.  Learning-based low-rank approximations.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 7400–7410, 2019.
  * [JLL+21] Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang.  Online facility location with predictions.  CoRR, abs/2110.08840, 2021.
  * [JLTZ21] 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.
  * [JPS20] 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.
  * [KKP13] 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.
  * [KPS18] Ravi Kumar, Manish Purohit, and Zoya Svitkina.  Improving online algorithms via ML predictions.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 9684–9693, 2018.
  * [LLMV20] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1859–1877. SIAM, 2020.
  * [LMH+21] 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.
  * [LMRX21] 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:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [LV18] 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ässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3302–3311. PMLR, 2018\.
  * [LV21] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  J. ACM, 68(4):24:1–24:25, 2021.
  * [Mey01] Adam Meyerson.  Online facility location.  In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 426–431. IEEE Computer Society, 2001.
  * [Mit18] Michael Mitzenmacher.  A model for learned bloom filters and optimizing by sandwiching.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 462–471, 2018.
  * [Mit20] 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 LIPIcs, pages 14:1–14:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [MS91] Lyle A. McGeoch and Daniel Dominic Sleator.  A strongly competitive randomized paging algorithm.  Algorithmica, 6(6):816–825, 1991.
  * [Sha12] Shai Shalev-Shwartz.  Online learning and online convex optimization.  Found. Trends Mach. Learn., 4(2):107–194, 2012.
  * [ST85] Daniel Dominic Sleator and Robert Endre Tarjan.  Amortized efficiency of list update and paging rules.  Commun. ACM, 28(2):202–208, 1985.
  * [Wei20] Alexander Wei.  Better and simpler learning-augmented online caching.  In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 60:1–60:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [WLW20] Shufan Wang, Jian Li, and Shiqiang Wang.  Online algorithms for multi-shop ski rental with machine learned advice.  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, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [WZ20] Alexander Wei and Fred Zhang.  Optimal robustness-consistency trade-offs for learning-augmented online algorithms.  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, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [Yao77] Andrew Chi-Chin Yao.  Probabilistic computations: Toward a unified measure of complexity.  In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222–227. IEEE Computer Society, 1977.
  * [You91] Neal Young.  On-line caching as cache size varies.  In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’91, pages 241–250, Philadelphia, PA, USA, 1991. Society for Industrial and Applied Mathematics.
  * [You94] Neal E. Young.  The k-server dual and loose competitiveness for paging.  Algorithmica, 11(6):525–541, 1994.