# Dynamic Algorithms for Packing-Covering LPs
via Multiplicative Weight Updates

Sayan Bhattacharya111Supported by Engineering and Physical Sciences Research
Council, UK (EPSRC) Grant EP/S03353X/1.
University of Warwick
<EMAIL_ADDRESS>Peter Kiss
University of Warwick
<EMAIL_ADDRESS>Thatchaphol Saranurak
University of Michigan
<EMAIL_ADDRESS>
###### Abstract

In the _dynamic linear program_ (LP) problem, we are given an LP undergoing
updates and we need to maintain an approximately optimal solution. Recently,
significant attention (e.g. [Gupta et al. STOC’17; Arar et al. ICALP’18, Wajc
STOC’20]) has been devoted to the study of special cases of dynamic packing
and covering LPs, such as the dynamic fractional matching and set cover
problems. But until now, there is no non-trivial dynamic algorithm for general
packing and covering LPs.

In this paper, we settle the complexity of dynamic packing and covering LPs,
up to a polylogarithmic factor in update time. More precisely, in the
_partially dynamic_ setting (where updates can either only relax or only
restrict the feasible region), we give near-optimal deterministic
$\epsilon$-approximation algorithms with polylogarithmic amortized update
time. Then, we show that both partially dynamic updates and amortized update
time are necessary; without any of these conditions, the trivial algorithm
that recomputes the solution from scratch after every update is essentially
the best possible, assuming SETH.

To obtain our results, we initiate a systematic study of the _multiplicative
weights update_ (MWU) method in the dynamic setting. As by-products of our
techniques, we also obtain the first online $(1+\epsilon)$-competitive
algorithms for both covering and packing LPs with polylogarithmic recourse,
and the first streaming algorithms for covering and packing LPs with linear
space and polylogarithmic passes.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Techniques
    3. 1.3 By-Products of Our Techniques
    4. 1.4 Roadmap for the Rest of the Paper
  2. 2 The Whack-a-Mole MWU Algorithm
    1. 2.1 Static Whack-a-Mole MWU Algorithm
    2. 2.2 Dynamic Whack-a-Mole MWU Algorithm for Covering LPs
    3. 2.3 Streaming Whack-a-Mole MWU Algorithm
    4. 2.4 Online Whack-a-Mole MWU Algorithm
    5. 2.5 Reductions to General Packing-Covering LPs
    6. 2.6 Challenges for Dynamic Whack-a-Mole MWU Algorithm for Packing LPs
  3. 3 The Greedy MWU Algorithm
    1. 3.1 Static Greedy MWU Algorithm [Qua20, You14]
    2. 3.2 An Overview of Our Dynamic Greedy MWU Algorithm
    3. 3.3 Handling Restricting (resp. Relaxing) Updates to a Packing (resp. Covering) LP
  4. 4 Conditional Lower Bounds
    1. 4.1 Proof of Theorem 4.3 \- part (i)
    2. 4.2 Proof of Theorem 4.3 \- part (ii)
  5. A Proofs of Theorem 2.12 and Lemma 2.13
  6. B Missing Proofs from Section 3.1
    1. B.1 Proof of Property 3.3
    2. B.2 Proof of Property 3.4
  7. C Complete Algorithm from Section 3.2
    1. C.1 Variables
    2. C.2 Algorithm
    3. C.3 Correctness
    4. C.4 Running Time
    5. C.5 Maintenance of an estimate of $\delta_{k}$ for Algorithm 2
    6. C.6 The Handling of Translation Updates

##  1 Introduction

Packing and covering linear programs (LPs) are defined as follows:

Covering LP $\mathbb{\mathrm{\mathbb{C}}}$:
$\displaystyle\min_{x\in\mathbb{R}_{\geq 0}^{n}}\\{c^{\top}x\mid Ax\geq b\\},$
Packing LP $\mathbb{\mathrm{\mathbb{P}}}$:
$\displaystyle\max_{y\in\mathbb{R}_{\geq 0}^{m}}\\{b^{\top}y\mid A^{\top}y\leq
c\\},$

where $A\in\mathbb{R}_{\geq 0}^{m\times n},b\in\mathbb{R}_{\geq
0}^{m},c\in\mathbb{R}_{\geq 0}^{n}$ contain only non-negative entries. The two
LPs are duals to each other, so we let $\mathrm{OPT}$ denote their shared
optimum. We say that $x$ is an _$\epsilon$ -approximation_ for
$\mathrm{\mathbb{C}}$ if $Ax\geq b$ and
$c^{\top}x\leq(1+\epsilon)\mathrm{OPT}$. Similarly, $y$ is an _$\epsilon$
-approximation_ for $\mathrm{\mathbb{P}}$ if $A^{\top}y\leq c$ and
$b^{\top}y\geq\mathrm{OPT}/(1+\epsilon)$.

Packing-covering LPs have a wide range of applications in various different
contexts, such as in approximation algorithms [LN93, Tre98], flow control
[BBR04], scheduling [PST95], graph embedding [PST95] and auction mechanisms
[ZN01]. Thus, a long line of work is concerned with the study of efficient
algorithms for packing-covering LPs [ZO15, AZO19, WRM15, KY14, You14, CQ18,
Qua20], and currently, it is known how to compute $\epsilon$-approximation in
$\tilde{O}(N/\epsilon)$ time [AZO19, WRM15]. Here, $N$ denotes the total
number of non-zero entries in the constraint matrix.222$\tilde{O}(\cdot)$
notation hides a $\operatorname{poly}(\log(\frac{NW}{\epsilon}))$ factor,
where $W$ is the ratio between the largest and smallest nonzero entries in the
LP.

In this paper, we consider a very natural dynamic setting, where an adversary
can update any entry of $A,b$ or $c$. After each update, the goal is to obtain
a new $\epsilon$-approximation quickly. Although this question has been
studied since the early 80’s [OvL80, OvL81, Epp91, AEM92, Mat93], all the
existing dynamic algorithms can only handle a very small number of variables
such as 2 or 3 (but they work for general LPs). In contrast, significant
attention [ACC+18, BHN19, BK21, GKKP17, Waj20] has recently been devoted to a
special case of dynamic packing and covering LPs: the dynamic fractional
matching and set cover problems. These new algorithms, however, are highly
specific and do not extend to general packing-covering LPs. For the latter,
the current best dynamic algorithm just recomputes a solution from scratch
after each update.

###  1.1 Our Results

We resolve the complexity of dynamic algorithms for general packing-covering
LPs, up to a polylogarithmic factor in the update time. The following are the
two key take-home messages from this paper. (1) In partially dynamic settings,
there are deterministic $\epsilon$-approximation algorithms for this problem
that have polylogarithmic amortized update times. (2) Both partially dynamic
updates and amortized update times are necessary: without any of these
conditions, the trivial algorithm which recomputes an $\epsilon$-approximation
to the input LP from scratch is essentially the best possible. Below, we
explain our results more formally.

We say an update is _relaxing_ $\mathbb{\mathrm{\mathbb{C}}}$ (and
_restricting $\mathrm{\mathbb{P}}$_) if $u$ increases an entry of $A$ or
decreases an entry of $b,c$. Note that $\mathrm{OPT}$ can only decrease due to
a relaxing update. In contrast, an update is _restricting_
$\mathbb{\mathrm{\mathbb{C}}}$ (and _relaxing $\mathrm{\mathbb{P}}$_) if it
decreases an entry of $A$ or increases an entry of $b,c$. A sequence of
updates to an LP is _partially dynamic_ if either {all of them are relaxing}
or {all of them are restricting}. Otherwise, the sequence of updates is _fully
dynamic_. Let $N$ denote the _maximum_ number of non-zero entries in the input
LP throughout the sequence of updates. Our main algorithmic result is the
following:

######  Theorem 1.1.

We can deterministically maintain an $\epsilon$-approximation to a packing-
covering LP going through $t$ partially dynamic updates in
$\tilde{O}\left(N/\epsilon^{3}+t/\epsilon\right)$ total update time. Thus, the
amortized update time of our algorithm is $\tilde{O}(1/\epsilon^{3})$.333The
total update time is defined to be the preprocessing time plus the total time
taken to handle all updates. If an algorithm has total update time
$O(N\tau_{1}+t\tau_{2})$, then its amortized update time is
$O(\max\\{\tau_{1},\tau_{2}\\})$.

By generality of packing and covering LPs, several applications immediately
follow. For example, Theorem 1.1 implies the first decremental
$(1+\epsilon)$-approximation algorithm for bipartite maximum matching in
weighted graphs in $\operatorname{poly}(\log(n)/\epsilon)$ amortized update
time. Previously, the best known algorithms either took $\Omega(\sqrt{m})$
update time [GP13] or only worked for unweighted graphs [BGS20, JJST22,
ABD22]. Theorem 1.1 also implies near-optimal incremental/decremental
algorithms for maintaining near-optimal fractional solutions for set covers
and dominating sets [GKKP17, HIPS19]. Generally, Theorem 1.1 reduces every
dynamic problem that can be modeled as a packing/covering LP to a dynamic
_rounding problem_. Since rounding LPs is one of the most successful paradigms
in designing approximation algorithms in the static setting, we expect that
our result will find many other future applications in dynamic algorithms.

We complement Theorem 1.1 by giving strong conditional lower bounds. Assuming
SETH,444The Strong Exponential Time Hypothesis [IPZ01] says that there is no
algorithm for solving $k$-CNF SAT with $n$ variables for all $k$ in
$2^{n-\Omega(1)}$ time. we show that a $N^{o(1)}$-approximation algorithm
which either handles fully dynamic updates or guarantees worst-case update
time, must have an update time of $\Omega(N^{1-o(1)})$. As we can solve the
problem from scratch after every update in $\tilde{O}(N)$ time, our lower
bound rules out any non-trivial dynamic algorithm in these settings.

######  Theorem 1.2.

Under SETH, there exists a $\beta=N^{o(1)}$ such that any dynamic algorithm
$\mathcal{A}$ that maintains a $\beta$-approximation to the optimal objective
of a packing or covering LP $\mathrm{\mathbb{P}}$ satisfies the following
conditions.

  * •

If $\mathrm{\mathbb{P}}$ undergoes fully dynamic updates, then ${\cal A}$ must
have $\Omega(N^{1-o(1)})$ amortized update time.

  * •

If $\mathrm{\mathbb{P}}$ undergoes partially dynamic updates, then ${\cal A}$
must have $\Omega(N^{1-o(1)})$ worst-case update time.

Our lower bounds hold even if the dynamic algorithm only _implicitly_
maintains the solution, meaning that it only maintains an approximation to the
value of $\mathrm{OPT}$. Furthermore, they hold even if all the updates are on
the entries of the constraint matrix $A$. Thus, Theorem 1.1 and Theorem 1.2
essentially settle the complexity of the dynamic packing-covering LP problem,
up to a polylogarithmic factor in update time.

###  1.2 Techniques

To prove our main result (Theorem 1.1), we initiate a systematic study of the
_multiplicative weight update_ (MWU) framework in the dynamic setting. MWU is
one the most versatile iterative optimization framework in theoretical
computer science. There is a big conceptual barrier, however, in extending
this framework to the dynamic setting. We start by explaining how to overcome
this conceptual barrier.

####  1.2.1 MWU in the dynamic setting: The main challenge

Like other iterative methods, a MWU-based algorithm builds its solution $x$ in
iterations. At each iteration $t$, the solution $x^{(t)}$ heavily depends on
the previous solution $x^{(t-1)}$. So when we update our original input, we
expect that the update affects the solution $x^{(1)}$ from the first
iteration. Then, the change in $x^{(1)}$ affects $x^{(2)}$, which in turn
affects $x^{(3)}$ and so on. There are at least logarithmic many iterations
and eventually the final solution might completely change. Intuitively, this
propagation of changes suggests that using MWU in the dynamic setting is a
dead end. How do we overcome this strong conceptual barrier?

As a take-home message, we show that for MWU there is no propagation of
changes under partially dynamic updates! To be a bit more concrete, suppose
that the current solution is $x^{(t)}$ and now the adversary updates the
input. As long as the updates are partially dynamic, we can argue that all the
previous solutions $x^{(1)},\dots,x^{(t-1)},x^{(t)}$ remain valid with the new
input. Our only task is to compute a valid $x^{(t+1)}$ for the updated input,
which is much more manageable. To understand why this is possible, we now
explain how MWU works at a high level.

The explanation below will be generic (i.e., it will hold beyond packing-
covering LPs). But for concreteness, consider a feasibility problem where
given a matrix $C\in\\{0,1\\}^{m\times n}$, we need to find
$x\in\mathbb{R}_{\geq 0}^{n}$ where $\mathbb{1}^{\top}x\leq 1$ and
$Cx\geq\mathbb{1}$. Its dual problem is to find $y\in\mathbb{R}_{\geq 0}^{m}$
where $\mathbb{1}^{\top}y\geq 1$ and $C^{\top}y\leq\mathbb{1}$. MWU-based
algorithms can be viewed as two-player games where the two players, which we
call a _Whack-a-Mole_ player and a _Greedy_ player, together maintain a pair
$(x,y)$ using the following simple outline:

  1. 1.

Whack-a-Mole player builds a multiplicative solution: Start with
$x=\mathbb{1}/n$. If $x$ violates some constraint $i\in[m]$ (i.e. $C_{i}x<1$),
then _multiplicatively_ update $x$ according to $i$ (i.e.
$x_{j}\leftarrow(1+\epsilon)x_{j}$ for all $j$ where $C_{ij}=1$). We refer to
this operation as _whacking_ constraint $i$. Whenever $x$ satisfies all
constraints, terminate the game. Basically, this player keeps “whacking”
violated constraints.

  2. 2.

Greedy player builds an additive solution:  Start with the zero vector
$y=\boldsymbol{0}$. If there exists a _cheap_ coordinate $i\in[m]$, then
_additively_ increment $y_{i}$ by one. (In our case, coordinate $i$ is cheap
iff $C_{i}x<1$.)555For readers familiar with the MWU literature, this is the
“oracle” problem. Given weight $x$, we need to find a $y^{\prime}$ which
satisfies the “average constraint” $x^{\top}C^{\top}y^{\prime}\leq x^{\top}1$.
Then, we set $y\leftarrow y+y^{\prime}$. Terminate the game after $T$ rounds,
for some $T$, and return the average $y^{*}=y/T$. Basically, this player keeps
greedily “incrementing” in a cheap direction.

The game terminates when: either (1) $x$ satisfying all constraints, or (2)
via the regret minimization property of MWU [AHK12], we can show that $y^{*}$
is approximately feasible (i.e., $\mathbb{1}^{\top}y^{*}=1$ and
$C^{\top}y^{*}\leq(1+\epsilon)\mathbb{1}$).

Coming back to the existing literature on MWU, we observe that the known
algorithms can be classified into one of two categories. The algorithms in the
first category take the greedy player’s perspective and build their solutions
$y$ additively, while updating the weight $x$ multiplicatively as a helper.
These include algorithms for flow-related problems [Fle00, GK02, GK07],
packing-covering LPs [PST95, KY14, You14, CQ18, Qua20], or constructions of
pseudorandom objects [Bsh16]. In contrast, the algorithms in the second
category take the whack-a-mole player’s perspective and build their solutions
$x$ multiplicatively. These include algorithms for learning and boosting
[Lit88, FS97, FS99]. The idea is also implicit in algorithms for geometric set
covers [Cla93, BG95, AP14, CH20] and explicit in algorithms for online set
covers [GKL21].

Now, the high-level explanation as to why MWU works under partially dynamic
updates is simple. Suppose that the updates are restricting only. Then we take
the whack-a-mole player’s perspective. All we do is whacking violated
constraints. Given an update, the constraints that we whacked in the past
would still be violated at that time because the update is restricting. So our
past actions are still valid. On the other hand, if the updates are relaxing
only, then we take the greedy player’s perspective. Given a relaxing update,
all the cheap directions that we incremented in the past remain cheap at the
present moment as well. This explains why all the past actions that we
committed to are still valid. Hence, we only need to ensure that the next
action is valid with respect to the updated input.

As the reasoning above is very generic, we expect that this insight will lead
to further applications. For now, we discuss how we efficiently carry out this
approach for packing-covering LPs.

####  1.2.2 Width-Independent Packing Covering LP Solvers via Black-box Regret
Minimization

Existing static $\epsilon$-approximation algorithms for packing-covering LPs
can be grouped into two types: _width-dependent_ and _width-independent_
solvers. The width-dependent solvers have running time depending on
$\lambda\cdot\mathrm{OPT}$, where $\lambda$ is the largest entry in the LP
(e.g. $\tilde{O}(N(\frac{\lambda\mathrm{OPT}}{\epsilon})^{2})$ [PST95] and
$\tilde{O}(N\frac{\lambda\mathrm{OPT}}{\epsilon^{2}})$ [AHK12]). While the
analysis in [PST95] is adhoc, [AHK12] gives a very insightful explanation as
to how the guarantee of these solvers follows in a black-box manner from the
well-established regret minimization property of MWU in the experts setting.
This undesirable dependency on $\lambda\mathrm{OPT}$ in the runtime led to an
extensive line of work on width-independent solvers [ZO15, KY14, You14, CQ18,
Qua20]. These stronger solvers run in
$\tilde{O}(N/\operatorname{poly}(\epsilon))$ time, which is independent of
$\lambda\mathrm{OPT}$, and many of them are based on MWU.

There is, however, one curious and unsatisfactory aspect in the literature on
width-independent LP solvers. Namely, each of these MWU-based algorithms
requires a separate and fine-tuned analysis involving calculations that
resemble the proof of the regret minimization property of MWU. But can we just
apply the regret bound of MWU in a blackbox manner while analyzing a width-
indepdendent LP solver?

We design a new static algorithm for packing-covering LPs that answers this
question in affirmative. To the best of our knowledge, it is the first width-
independent near-linear-time LP solver whose analysis follows from a black-box
application of the regret bound for MWU. This is explained in details in
Section 2.1. Moreover, the algorithm is very intuitive and its high-level
description is as follows:

> There are $O(\log(n)/\epsilon^{2})$ phases. During each phase, we loop over
> the constraints: if constraint $i$ is violated, then we “whack” it until it
> is satisfied and move on to the next constraint $i+1$. Whenever
> $\mathbb{1}^{\top}x>(1+\epsilon)$, we start the next phase and normalize $x$
> so that $\mathbb{1}^{\top}x=1$. If we finish the loop, then we return $x$ as
> an $\epsilon$-approximation to the primal. After the last phase, we are
> guaranteed to obtain a dual $\epsilon$-approximation $y$ certifying that
> there is “almost” no feasible primal solution, i.e., no $x$ where
> $\mathbb{1}^{\top}x\leq 1$ and $Cx\geq(1+\epsilon)\cdot\mathbb{1}$.

Henceforth, we refer to this algorithm as the _whack-a-mole MWU
algorithm_.666Our algorithm resembles the whack-a-mole-based algorithms for
computing geometric set covers [Cla93, BG95, AP14, CH20]. However, these
previous algorithms give $O(1)$-approximation, are specifically described for
set covers, and use adhoc calculation related to MWU. Thus, our whack-a-mole
MWU algorithm refines their approximation, generalizes their applicability,
and modularizes their analysis. Furthermore, for readers familiar with the
algorithms of [You14, Qua20], our whack-a-mole MWU algorithms can be
interpreted as implementing their algorithms from the whack-a-mole player’s
perspective.  The algorithm takes near-linear time because it has few phases
and each phase requires only one-pass scan. In more details, we refer to the
operation of “whacking constraint $i$ until it is satisfied” as _enforceing_
constraint $i$. Enforcing a constraint $i$ can be done via binary search in
$\tilde{O}(N_{i})$ time, where $N_{i}$ is the number of non-zero entries in
constraint $i$. As each constraint is scanned and enforced once per phase, the
total running time is $\tilde{O}(\sum
N_{i}/\epsilon^{2})=\tilde{O}(N/\epsilon^{2})$.

The simplicity of this algorithm not only leads us to efficient dynamic
implementations (see Section 1.2.3), but also efficient streaming algorithms
and online algorithms with recourse (see Section 1.3).

####  1.2.3 Dynamic Implementation

We can extend our whack-a-mole MWU algorithm from Section 1.2.2 to handle
restricting updates, in the following natural manner. Suppose that the
algorithm obtained a feasible solution $x$ (because $x$ satisfies all
constraints during the one-pass scan). Now, consider a restricting update to
constraint $i$, say to an entry $C_{ij}$. We just need to check whether $x$
violates constraint $i$ (i.e., if $C_{i}x<1$). If yes, then we enforce
constraint $i$ (i.e., whack it until it is satisfied). No new constraint gets
violated due to this enforcement. As in the static setting, we start the next
phase whenever $\mathbb{1}^{\top}x>(1+\epsilon)$. We proceed like this until
we obtain a feasible solution $x$. Once the algorithm concludes that there is
almost no feasible solution, then we are done because this will remain the
case after future restricting updates. The correctness follows from the static
algorithm.

We have to overcome an issue while analyzing the total update time: Each
constraint is _not_ enforced once per phase anymore (because constraint $i$
can be updated repeatedly within a phase). Accordingly, we strengthen our
analysis to show that, even under restricting updates, each constraint is
still enforced $\tilde{O}(1/\epsilon^{2})$ times. But the algorithm remains
the same. This leads to a total update time of $\tilde{O}(N/\epsilon^{2}+t)$,
for $t$ updates.

Our dynamic whack-a-mole MWU algorithm applies to covering LPs under
restricting updates, and by duality, to packing LPs under relaxing updates.
There is a technical challenge, however, that prevents us from extending this
approach to packing (resp. covering) LPs under restricting (resp. relaxing)
updates.

To handle this case, we instead consider another static
$\tilde{O}(N/\epsilon^{2})$-time algorithm that take the greedy player’s
perspective [You14, Qua20]. We call it the _greedy MWU algorithm_. Given a
covering LP (or even a mixed packing-covering LP), this greedy MWU algorithm
can naturally handle relaxing updates (as discussed in Section 1.2.1). Using
similar ideas, we show how to dynamize it with only polylogarithmic overhead
in the total update time. Therefore, we obtain algorithms for covering LPs
under relaxing updates, and by duality, for packing LPs under restricting
update via duality.777Since the greedy MWU algorithm can handle mixed packing-
covering LPs under relaxing updates, via duality this implies algorithms for
handling restricting updates to both covering and packing LPs. So strictly
speaking, our dynamic whack-a-mole MWU algorithm is subsumed by the dynamic
greedy MWU algorithm. Nevertheless, we present the dynamic whack-a-mole MWU
algorithm as it is simpler to understand and has more modular analysis.

##### Discussion on the Simplicity of Our Techniques.

We show how to seamlessly use the MWU framework to obtain near-optimal
partially dynamic algorithms for packing-covering LPs. We view the simplicity
of our approach as an important merit of this paper. Despite its simplicity,
our result implies immediate applications such as a near-optimal decremental
maximum weight matching algorithm, while previous algorithms [BGS20, JJST22]
for this problem require more involved arguments and work only on unweighted
graphs.

###  1.3 By-Products of Our Techniques

Our techniques turn out to have implications beyond dynamic algorithms for
packing-covering LPs.

##### Online Algorithms with Recourse.

The online covering LP problem was introduced in the influential work of
Buchbinder and Naor [BN09a]. This is a fundamental problem in the literature
on the online primal-dual method; with applications in online set cover,
routing, ad-auctions, metrical task systems and many other settings (see the
book [BN+09b]). Several variants of the problem are studied in [GN12, ABFP13,
GKL21].

In this problem, we have a covering LP $\mathrm{\mathbb{C}}$ with $m$
constraints and $n$ variables. The constraints of $\mathrm{\mathbb{C}}$ arrive
in an online fashion one after another, and we need to maintain a solution to
$\mathrm{\mathbb{C}}$. Crucially, the values of the variables can only
increase through time (i.e., any decision made cannot be retracted). An online
covering LP algorithm is $\alpha$-competitive if it maintains a solution to
$\mathrm{\mathbb{C}}$ whose cost is always at most $\alpha\cdot\mathrm{OPT}$.
Buchbinder and Naor gave a tight $\Theta(\log n)$-competitive algorithm for
this problem.

Can we beat the lower bound on competitive ratio for a given problem by
allowing some amount of _recourse_? Here, recourse is defined to be the number
of times the algorithm “retracts” its decision. An influential line of work in
online algorithms [BHR18, GGK13, GK14, GKS14, GKKP17] has been devoted towards
answering this question for various fundamental problems. For online covering
LPs, recourse equals the number of times the value of any variable is
decreased. Although covering LPs play a central role in online algorithms,
until now it was not known whether we can beat the $\Omega(\log n)$ lower
bound on the competitive ratio of this problem if we allow for small recourse.
We answer this question in the affirmative.

######  Theorem 1.3.

There is a $(1+\epsilon)$-competitive algorithm for online covering LPs with
$O(n\log(n)\log(nW)/\epsilon^{3})$ total recourse. In fact, in this algorithm
each variable incurs at most $O(\log(n)\log(nW)/\epsilon^{3})$ recourse.

Note that the recourse bound is completely independent of the number of
constraints. Theorem 1.3 follows almost immediately from our whack-a-mole MWU
algorithm from Section 1.2.2. Interestingly, our algorithm can be viewed as a
small adjustment to the well-known $O(\log n)$-competitive algorithm of
[BN09a]. To see this, suppose that we know $\mathrm{OPT}$ by guessing. Then
here is the description of our algorithm.

> Run the algorithm of [BN09a]. Whenever the objective of the solution exceeds
> $(1+\epsilon)\mathrm{OPT}$, scale down the solution by a factor of
> $(1+\epsilon)$ and continue.

Our argument shows that we will never scale down too many times. The algorithm
is clearly $(1+\epsilon)$-competitive. In the paper, we also show similar
$(1+\epsilon)$-competitive algorithm for online packing LPs. Curiously, online
algorithms _without_ recourse of this problem is not known.888Many papers in
online algorithms consider a problem where the _variables_ of a packing LP are
revealed one by one, which is a dual of the online covering LP problem. We
consider a different setting, where the packing constraints arrive one after
another.

##### Streaming algorithms.

Our whack-a-mole MWU algorithm also works in the streaming setting. When the
rows of the constraint matrix arrive one by one, we obtain an
$\epsilon$-approximation for both packing and covering LPs using $O(n)$ space
and $\tilde{O}(1/\epsilon^{3})$ passes. In contrast, when the columns of the
constraint matrix arrive one by one, we get the same result but with a space
complexity of $O(n+m)$. These give the first streaming algorithms for general
packing covering LPs. Previous algorithms in the literature worked only for
special cases such as fractional set cover [IMR+17] and fractional matching
[AG11, AG18, AJJ+22].

##### Mixed Packing-Covering LPs.

In a _mixed packing-covering_ LP $\mathrm{\mathbb{P}}$ (or _positive_ LP for
short), we are given $A_{c}\in\mathbb{R}_{\geq 0}^{m_{c}\times
n},b_{c}\in\mathbb{R}_{\geq 0}^{m_{c}}$ and $A_{p}\in\mathbb{R}_{\geq
0}^{m_{p}\times n},b_{p}\in\mathbb{R}_{\geq 0}^{m_{p}}$, and we need to find
$x\in\mathbb{R}_{\geq 0}^{n}$ such that $A_{c}x\geq b_{c}$ and $A_{p}x\leq
b_{p}$. This is a generalization of both packing and covering LPs. An $x$ is
an $\epsilon$-approximation to this positive LP if $A_{c}x\geq
b_{c}/(1+\epsilon)$ and $A_{p}x\leq(1+\epsilon)b_{p}$. Our dynamic greedy MWU
algorithm can handle positive LPs under relaxing updates.

######  Theorem 1.4.

We can deterministically maintain an $\epsilon$-approximation to a positive LP
undergoing $t$ relaxing updates in
$\tilde{O}\left(N/\epsilon^{3}+t/\epsilon\right)$ total update time. Hence,
the amortized update time of our algorithm is $\tilde{O}(1/\epsilon^{3})$.

Theorem 1.4 immediately gives the following natural applications captured by
mixed packing-covering LPs. For the well-studied load balancing problem (e.g.,
[HLLT06, ABL20]), we obtain a near-optimal decremental algorithm for
maintaining $(1+\epsilon)$-approximate fractional assignments, where each
update deletes a job. By duality, for the dynamic densest subhypergraph
problem [HWC17, BBCG22], this implies a near-optimal decremental algorithm for
maintaining $(1+\epsilon)$-approximation, where each update deletes a
hyperedge. The near-optimal algorithms for both problems were not known
before.

Finally, we leave the question of designing a dynamic algorithm for positive
LPs under restricting updates as an interesting open problem.

###  1.4 Roadmap for the Rest of the Paper

In Section 2, we present our whack-a-mole MWU algorithm and its extensions to
dynamic, streaming and online settings. Section 3 gives an overview of the
static greedy MWU algorithm for positive LPs [You14, Qua20], and then explains
how we extend this algorithm to the setting where the input LP undergoes
relaxing updates. Finally, in Section 4, we present our conditional lower
bounds for dynamic packing-covering LPs.

If the reader wishes to treat this as an extended abstract, then we recommend
reading until the end of Section 2.2 as that contains the main technical
result of this paper.

##  2 The Whack-a-Mole MWU Algorithm

This section focuses on the whack-a-mole MWU algorithm. We start by
considering the following problem.

######  Problem 2.1.

Given a matrix $C\in[0,\lambda]^{m\times n}$ where $\lambda>0$, either return
a vector $x\in\mathbb{R}_{\geq 0}^{n}$ with $\mathbb{1}^{\top}x\leq
1+\Theta(\epsilon)$ and $Cx\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$, or return
a vector $y\in\mathbb{R}_{\geq 0}^{m}$ with $\mathbb{1}^{\top}y\geq
1-\Theta(\epsilon)$ and $C^{\top}y\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$.

Problem 2.1 corresponds to the following covering LP: $\text{Minimize
}\mathbb{1}^{\top}x,\text{ s.t. }Cx\geq\mathbb{1}\text{ and
}x\in\mathbb{R}_{\geq 0}^{n}$. We have to either return an approximately
feasible solution to this covering LP with objective $\leq
1+\Theta(\epsilon)$, or return an approximately feasible solution to the dual
packing LP with objective $\geq 1-\Theta(\epsilon)$. In Sections 2.1, 2.2, 2.3
and 2.4, we respectively show that our MWU algorithm solves Problem 2.1 in
static, dynamic, streaming and online settings. Subsequently, in Section 2.5,
we explain how we can compute an $\epsilon$-approximate optimal solution to a
general packing-covering LP if we have an algorithm for Problem 2.1.

Throughout this section, an index $i\in[m]$ (resp. $j\in[n]$) refers to a row
(resp. column) of the matrix $C$, and $C_{ij}\in[0,\lambda]$ denotes the entry
corresponding to the $i^{th}$ row and $j^{th}$ column of $C$. Furthermore, the
symbol $v_{k}$ denotes the $k^{th}$ coordinate of a vector
$v\in\mathbb{R}^{n}$, where $k\in[n]$.

###  2.1 Static Whack-a-Mole MWU Algorithm

We now present the whack-a-mole MWU algorithm for Problem 2.1 in the static
setting. We describe the basic template behind the algorithm in Section 2.1.1.
In Section 2.1.3, we show how to implement this basic template in near-linear
time.

####  2.1.1 The Basic Template

01. Define $T\leftarrow\frac{\lambda\ln(n)}{\epsilon^{2}}$, and two vectors $\hat{x}^{1},x^{1}\in\mathbb{R}_{\geq 0}^{n}$ where $\hat{x}^{1}\leftarrow\mathbb{1}$ and $x^{1}\leftarrow\frac{\hat{x}^{1}}{\left\lVert\hat{x}^{1}\right\rVert_{1}}$. 02. For $t=1$ to $T$: 03. Either 04. Conclude that $\left(C\cdot x^{t}\right)_{i}\geq 1-\epsilon$ for all $i\in[m]$. 05. Terminate the For loop, and Return $(x^{t},\text{{\sc Null}})$. 06. Or 07. Find a covering constraint $i_{t}\in[m]$ such that $\left(C\cdot x^{t}\right)_{i_{t}}<1$. 08. $\hat{x}^{t+1}\leftarrow\text{\sc{Whack}}(i_{t},\hat{x}^{t})$. // See Figure 2. 09. $x^{t+1}\leftarrow\frac{\hat{x}^{t+1}}{\left\lVert\hat{x}^{t+1}\right\rVert_{1}}$. 10. Let $y^{t}\in\Delta^{m}$ be the vector where $\left(y^{t}\right)_{i_{t}}=1$ and $\left(y^{t}\right)_{i}=0$ for all $i\in[m]\setminus\\{i_{t}\\}$. 11. $y\leftarrow(1/T)\cdot\sum_{t=1}^{T}y^{t}$. 12. Return $(\text{{\sc Null}},y)$.

Figure 1:  The Whack-a-Mole MWU Algorithm

1. For all $j\in[n]$: 2. $\hat{z}_{j}\leftarrow\left(1+\epsilon\cdot\frac{C_{ij}}{\lambda}\right)\cdot\hat{x}_{j}$. 3. Return $\hat{z}$

Figure 2:  Whack$(i,\hat{x})$.

The algorithm is described in Figure 1 and Figure 2. It maintains a vector
$\hat{x}\in\mathbb{R}_{\geq 0}^{n}$, where $\hat{x}_{j}$ denotes the weight
associated with a variable $j\in[n]$ in the covering LP, and the normalized
vector $x:=\hat{x}/\left\lVert\hat{x}\right\rVert_{1}$. This ensures that
$\mathbb{1}^{\top}\cdot x=1$. The algorithm runs in
$T=\lambda\ln(n)/\epsilon^{2}$ iterations, where $0<\epsilon<1/2$.

Let $\hat{x}^{t}$ and $x^{t}$ respectively denote the status of $\hat{x}$ and
$x$ at the start of iteration $t\in[T]$ of the main For loop in Figure 1.
Before the very first iteration, we initialize
$\hat{x}^{1}\leftarrow\mathbb{1}$. Subsequently, during any given iteration
$t\in[T]$, the algorithm branches into one of the following two cases.

Case (1). It observes that $Cx^{t}\geq(1-\epsilon)\cdot\mathbb{1}$ and returns
$(x^{t},\text{{\sc Null}})$. In this case, $x^{t}\in\mathbb{R}_{\geq 0}^{n}$
is an approximately feasible solution to the covering LP, with objective
$\mathbb{1}^{\top}x^{t}=1$.

Case (2). It identifies a violated covering constraint $i_{t}\in[m]$ with
$\left(Cx^{t}\right)_{i_{t}}<1$. It then whacks constraint $i_{t}$, by setting
$\hat{x}_{j}\leftarrow\left(1+\epsilon\cdot\frac{C_{i_{t}j}}{\lambda}\right)\cdot\hat{x}_{j}$
for all $j\in[n]$, and accordingly updates the normalized vector $x$. Note
that this step increases the relative importance (in the solution $x^{t}$) of
the coordinates $j\in[n]$ that have large $C_{i_{t}j}$ values. Thus,
intuitively, whacking a violated covering constraint makes progress towards
making the solution $x^{t}$ feasible for the covering LP. We let
$y^{t}\in\Delta^{m}$ denote the indicator vector for the covering constraint
$i_{t}\in[m]$ that gets whacked.

After $T$ iterations, the algorithm returns $(\text{{\sc Null}},y)$, where $y$
is the average of the vectors $y^{1},\cdots,y^{T}$. Clearly, we have
$\mathbb{1}^{\top}y=1$. The next lemma shows that $y$ is an approximately
feasible solution to the dual packing LP.999We remark here that this basic
algorithm will work even if the matrix $C$ had negative entries (i.e., if we
had $C\in[-\lambda,\lambda]^{m\times n}$), provided we increase the number of
iterations by setting $T=\frac{\lambda^{2}\ln(n)}{\epsilon^{2}}$. Its proof
appears in Section 2.1.2.

######  Lemma 2.2.

Suppose that the algorithm in Figure 1 returns $(\text{{\sc Null}},y)$ in step
(12). Then $C^{\top}y\leq(1+4\epsilon)\cdot\mathbb{1}$.

######  Theorem 2.3.

The algorithm in Figure 1 either returns an $x^{t}\in\mathbb{R}_{\geq 0}^{n}$
with $\mathbb{1}^{\top}x^{t}=1$ and $Cx^{t}\geq(1-\epsilon)\cdot\mathbb{1}$,
or it returns a $y\in\mathbb{R}_{\geq 0}^{m}$ with $\mathbb{1}^{\top}y=1$ and
$C^{\top}y\leq(1+4\epsilon)\cdot\mathbb{1}$.

###### Proof.

Follows from Lemma 2.2 and the preceding discussion. ∎

####  2.1.2 Proof of Lemma 2.2

We start by recalling the experts setting [AHK12]. We have $n$ experts
$\\{1,\ldots,n\\}$, who participate the following process that goes on for $T$
rounds. At the start of round $t\in[T]$, we have a weight vector
$w^{t}\in\mathbb{R}_{\geq 0}^{n}$, where $\left(w^{t}\right)_{j}$ denotes the
weight associated with expert $j\in[n]$. Initially, before round $1$ begins,
we set $w^{t}=\mathbb{1}$. These weights define a distribution
$\mathcal{D}^{t}$ over the experts, where the probability of picking expert
$j\in[n]$ is given by $\frac{\left(w^{t}\right)_{j}}{\left\lVert
w^{t}\right\rVert_{1}}$. At the start of round $t\in[T]$, our algorithm picks
an expert $j\in[n]$ from this distribution $\mathcal{D}^{t}$. Subsequently,
nature reveals a payoff vector $p^{t}\in[-1,1]^{n}$, where
$\left(p^{t}\right)_{j}\in[-1,1]$ is the payoff for expert $j\in[n]$ in round
$t$. Based on these payoffs, the algorithm then updates the weights of the
experts for the next round, by setting
$w^{t+1}_{j}\leftarrow\left(1+\epsilon\cdot\left(p^{t}\right)_{j}\right)\cdot
w^{t}_{j}$ for all $j\in[n]$.

The lemma below, which is identical to Theorem $2.5$ in [AHK12], bounds the
total expected payoff obtained by the algorithm in this setting, in terms of
the total payoff obtained by any fixed expert.

######  Lemma 2.4.

For all experts $j\in[n]$, we have:

$\sum_{t=1}^{T}\left(p^{t}\right)^{\top}\cdot\frac{w^{t}}{\left\lVert
w^{t}\right\rVert_{1}}\geq\sum_{t=1}^{T}\left(p^{t}\right)_{j}-\sum_{t=1}^{T}\epsilon\cdot\left|\left(p^{t}\right)_{j}\right|-\frac{\ln(n)}{\epsilon}.$

We now map the whack-a-mole algorithm to the experts setting as follows. Each
covering constraint $j\in[n]$ corresponds to an expert, each iteration of the
For loop in Figure 1 corresponds to a round, the vector $\hat{x}^{t}$
corresponds to the weight vector $w^{t}$ at the start of round $t\in[T]$, and
finally, the payoff for an expert $j\in[n]$ in round $t\in[T]$ is given by
$\left(p^{t}\right)_{j}:=(1/\lambda)\cdot C_{i_{t},j}$.

Since $C_{i_{t},j}\in[0,\lambda]$, we have
$\left|\left(p^{t}\right)_{j}\right|=\left(p^{t}\right)_{j}$ for all
$j\in[n],t\in[T]$. Thus, Lemma 2.4 implies that:

$\displaystyle\sum^{T}_{t=1}\left(p^{t}\right)^{\top}\cdot
x^{t}\geq\sum_{t=1}^{T}(1-\epsilon)\cdot\left(p^{t}\right)_{j}-\frac{\ln(n)}{\epsilon},\text{
for all experts }j\in[n].$ (2.1)

Diving both sides of the above inequality by $T$, and then rearranging the
terms, we get:

$\displaystyle\frac{(1-\epsilon)}{T}\cdot\sum_{t=1}^{T}\left(p^{t}\right)_{j}\leq\frac{1}{T}\cdot\sum^{T}_{t=1}\left(p^{t}\right)^{\top}\cdot
x^{t}+\frac{\ln(n)}{\epsilon\cdot T},\text{ for all experts }j\in[n].$ (2.2)

We next upper bound the right hand side (RHS) of (2.2). Since the algorithm
picks a violated covering constraint to whack in each round, we have:
$\left(p^{t}\right)^{\top}\cdot
x^{t}=(1/\lambda)\cdot\left(Cx^{t}\right)_{i_{t}}\leq(1/\lambda)$. Taking the
average of this inequality across all the $T$ rounds, we get:
$(1/T)\cdot\sum^{T}_{t=1}\left(p^{t}\right)^{\top}\cdot x^{t}\leq(1/\lambda)$.
Since $T=\lambda\ln(n)/\epsilon^{2}$, we derive the following upper bound on
the RHS of (2.2).

$\displaystyle\frac{1}{T}\cdot\sum^{T}_{t=1}\left(p^{t}\right)^{\top}\cdot
x^{t}+\frac{\ln(n)}{\epsilon\cdot T}\leq\frac{1}{\lambda}\cdot(1+\epsilon).$
(2.3)

We now focus our attention on the left hand side (LHS) of (2.2). Fix any
expert $j\in[n]$. We first express the payoff obtained by this expert at round
$t\in[T]$ in terms of the vector $y^{t}$, and get:
$\left(p^{t}\right)_{j}=\frac{1}{\lambda}\cdot
C_{i_{t},j}=\frac{1}{\lambda}\cdot\left(C^{\top}y^{t}\right)_{j}$. Since
$y=\frac{1}{T}\cdot\sum_{t=1}^{T}y^{t}$, the average payoff for the expert $j$
across all the $T$ rounds is given by:

$\displaystyle\frac{1}{T}\cdot\sum_{t=1}^{T}\left(p^{t}\right)_{j}=\frac{1}{T}\cdot\frac{1}{\lambda}\cdot\sum_{t=1}^{T}\left(C^{\top}y^{t}\right)_{j}=\frac{1}{\lambda}\cdot\left(C^{\top}y\right)_{j}.$
(2.4)

From (2.2), (2.3) and (2.4), we get:

$\frac{(1-\epsilon)}{\lambda}\cdot\left(C^{\top}y\right)_{j}\leq\frac{1}{\lambda}\cdot(1+\epsilon),\text{
and hence }\left(C^{\top}y\right)_{j}\leq(1+4\epsilon)\text{ for all
}j\in[n].$

The last inequality holds since $\epsilon<1/2$. This concludes the proof of
Lemma 2.2.

####  2.1.3 A Near-Linear Time Implementation

01. $\hat{x}^{1}\leftarrow\mathbb{1}$, $t\leftarrow 1$, and $T\leftarrow\lambda\ln(n)/\epsilon^{2}$. 02. Loop 03. $W\leftarrow\left\lVert\hat{x}^{t}\right\rVert_{1}$. 04. For all $i\in[m]$: 05. If $\left(C\cdot\frac{\hat{x}^{t}}{W}\right)_{i}<1-\epsilon/2$ Then 06. $\delta\leftarrow\text{{\sc Enforce}}(i,t,\hat{x}^{t},W)$. // See Figure 4. 07. $t\leftarrow t+\delta$. 08. If $t=T$, Then 09. Terminate the Loop and return $(\text{{\sc Null}},y)$, where $y:=(1/T)\cdot\sum_{t^{\prime}=1}^{T}y^{t^{\prime}}$. 10. If $\left\lVert\hat{x}^{t}\right\rVert_{1}>(1-\epsilon/2)^{-1}\cdot W$, Then 11. Go to step (03). // Initiate a new phase. 12. Terminate the Loop and return $(x^{t},\text{{\sc Null}})$, where $x^{t}:=\frac{\hat{x}^{t}}{\left\lVert\hat{x}^{t}\right\rVert_{1}}$.

Figure 3:  An Implementation of the Whack-a-mole MWU Algorithm.

We now show how to implement the whack-a-mole MWU algorithm from Section 2.1.1
in near-linear time. This implementation is outlined in Figure 3, and is based
on two key ideas. (1) We split up the working of the Whack-a-mole MWU
algorithm into phases, and ensure that within any given phase the total weight
$\left\lVert\hat{x}^{t}\right\rVert_{1}$ of all the experts (see the
discussion in the beginning of Section 2.1.2) changes by at most a
$(1-\epsilon/2)^{-1}$ multiplicative factor. (2) The weight of an expert
$j\in[n]$ can only increase during the course of the algorithm. Because of
this, within a given phase we only need to consider each constraint at most
once, provided upon considering the constraint we keep repeatedly whacking it
until it gets satisfied.

At the start of a new phase, we set
$W\leftarrow\left\lVert\hat{x}^{t}\right\rVert_{1}$. Throughout the phase, the
value of $W$ will not change and it will serve as an estimate of the total
weight of the experts. Since $W$ remains within a multiplicative
$(1-\epsilon/2)^{-1}$ factor of $\left\lVert\hat{x}^{t}\right\rVert_{1}$, the
vector $\frac{\hat{x}^{t}}{W}$ remains a good estimate of the actual solution
$x^{t}:=\frac{\hat{x}^{t}}{\left\lVert\hat{x}^{t}\right\rVert_{1}}$.

1. $\delta\leftarrow\text{{\sc Step-size}}(i,t,\hat{x}^{t},W)$. // See Figure 5. 2. For $t^{\prime}=t$ to $(t+\delta-1)$: 3. $\hat{x}^{t^{\prime}+1}\leftarrow\text{{\sc Whack}}(i,\hat{x}^{t^{\prime}})$. // See Figure 2. 4. $i_{t^{\prime}}\leftarrow i$. 5. Let $y^{t^{\prime}}\in\Delta^{m}$ be the vector where $\left(y^{t^{\prime}}\right)_{i}=1$ and $\left(y^{t^{\prime}}\right)_{i^{\prime}}=0$ for all $i^{\prime}\in[m]\setminus\\{i\\}$. 6. Return $\delta$.

Figure 4:  Enforce$(i,t,\hat{x}^{t},W)$.

1. For every integer $\kappa\geq 1$, let $z^{\kappa}\in\mathbb{R}_{\geq 0}^{n}$ be such that $\left(z^{\kappa}\right)_{j}=\left(1+\epsilon\cdot\frac{C_{ij}}{\lambda}\right)^{\kappa}\cdot\left(\hat{x}^{t}\right)_{j}$ for all $j\in[n]$. 2. If $\left(C\cdot\frac{z^{T-t}}{W}\right)_{i}<1$, Then 3. $\delta\leftarrow T-t$. 4. Else 5. Using binary search, compute the the smallest integer $\delta\in[T-t]$ such that $\left(C\cdot\frac{z^{\delta}}{W}\right)_{i}\geq 1$. 6. Return $\delta$

Figure 5:  Step-size$(i,t,\hat{x}^{t},W)$

During a given phase, we scan through all the covering constraints in any
arbitrary order. We now explain how to implement a typical iteration of this
scan, where (say) we are considering the constraint $i\in[m]$. We first check
if $\left(C\cdot\frac{\hat{x}^{t}}{W}\right)_{i}\geq 1-\epsilon/2$, that is,
whether the constraint is approximately satisfied. If the answer is yes, then
we do nothing with this constraint and proceed to the next iteration of the
scan. In contrast, if the answer is no, then we enforce this constraint by
calling the subroutine Enforce$(i,t,\hat{x}^{t},W)$. This subroutine works as
follows. It finds an integer $\delta\geq 1$ which indicates the minimum number
of times the constraint $i\in[m]$ needs to be whacked before it gets
satisfied, assuming that we continue to be in the same phase even at the end
of all these whacks. Constraint $i$ then repeatedly gets whacked $\delta$
times, and after that we set $t\leftarrow t+\delta$. At this point, if $t=T$,
then we terminate the algorithm and return a solution for the dual packing LP,
as in Section 2.1.1. Else if
$\left\lVert\hat{x}^{t}\right\rVert_{1}>(1-\epsilon/2)^{-1}\cdot W$, because
the total weight of the experts increased a lot due to the previous $\delta$
whacks, then we initiate a new phase.

If at the end of the scan, we observe that $W$ is still an accurate estimate
of the total weight $\left\lVert\hat{x}^{t}\right\rVert_{1}$ and $t<T$, then
we terminate the algorithm and return
$x^{t}:=\frac{\hat{x}^{t}}{\left\lVert\hat{x}^{t}\right\rVert_{1}}$ as a
solution to the primal covering LP.

######  Lemma 2.5.

The procedure described in Figure 3 implements the algorithm from Section
2.1.1.

###### Proof.

We refer to each call to Whack$(i,\hat{x}^{t})$ as a round (see Section
2.1.2). Both Figure 1 and Figure 3 initialize
$\hat{x}^{1}\leftarrow\mathbb{1}$ and run for at most
$T=\lambda\ln(n)/\epsilon^{2}$ rounds. We will show that the way Figure 3
implements each round and the way it eventually returns a solution are both
consistent with Figure 1.

Towards this end, first consider the scenario where the procedure in Figure 3
enforces a constraint $i\in[m]$ at the start of a round $t\in[T]$ by calling
the subroutine Enforce$(i,t,\hat{x}^{t},W)$, which repeatedly whacks the
constraint $\delta$ times. From Figure 4 and Figure 5, we infer that

$\left(C\cdot\frac{\hat{x}^{t^{\prime}}}{W}\right)_{i}<1\text{ for all }t\leq
t^{\prime}\leq t+\delta-1.$ (2.5)

Since $W$ is the total weight of all the experts at the start of the concerned
phrase, and since the weight of any expert can only increase with time, we
have: $\left\lVert x^{t^{\prime}}\right\rVert_{1}\geq W$ for all
$t^{\prime}\geq t$. Hence, from (2.5) we get:

$\left(C\cdot x^{t^{\prime}}\right)_{i}<1\text{ for all }t\leq t^{\prime}\leq
t+\delta-1,\text{ where
}x^{t^{\prime}}:=\frac{\hat{x}^{t^{\prime}}}{\left\lVert
x^{t^{\prime}}\right\rVert_{1}}.$ (2.6)

This implies that the decisions to whack constraint $i\in[m]$ in successive
rounds $t^{\prime}\in[t,t+\delta-1]$ are consistent with the rule governing
the whacking of constraints in Figure 1.

Next, note that after enforcing the constraint $i\in[m]$, the procedure in
Figure 3 sets $t\leftarrow t+\delta$. At this point, if $t=T$, then it decides
to return the vector $y:=(1/T)\cdot\sum_{t^{\prime}=1}^{T}y^{t^{\prime}}$ as a
solution to the dual packing LP. Clearly, this decision is also consistent
with steps (11) – (12) in Figure 1.

Finally, consider the scenario where the procedure in Figure 3 returns a
vector $x^{t^{\prime\prime}}$ in round $t^{\prime\prime}$ (see step (12) in
Figure 3). Focus on the very last phase, which spans from (say) round
$t^{\prime}$ to round $t^{\prime\prime}$, where $t^{\prime}<t^{\prime\prime}$.
Let $W$ be the value of $\left\lVert\hat{x}^{t}\right\rVert_{1}$ at the start
of this phase. Fix any constraint $i\in[m]$, which was considered (say) at the
start of round $t_{i}\in[t^{\prime},t^{\prime\prime}]$ by the For loop in
Figure 3. Now, there are two possible cases.

Case I: The constraint $i$ did not get enforced in this phase. This happens if
$\left(C\cdot\frac{\hat{x}^{t_{i}}}{W}\right)_{i}\geq 1-\epsilon/2$. Here, we
derive that
$\left(C\cdot\frac{\hat{x}^{t^{\prime\prime}}}{W}\right)_{i}\geq\left(C\cdot\frac{\hat{x}^{t_{i}}}{W}\right)_{i}\geq
1-\epsilon/2$, since each co-ordinate of $\hat{x}$ can only increase over
time.

Case II: The constraint $i$ got enforced in this phase, by getting repeatedly
whacked $\delta$ times starting from round $t_{i}$. Thus, we have
$t_{i}+\delta<T$ (otherwise, the algorithm would return a dual packing
solution $y$) and $\left(C\cdot\frac{\hat{x}^{t_{i}+\delta}}{W}\right)_{i}\geq
1$. Analogous to Case I, here we derive that
$\left(C\cdot\frac{\hat{x}^{t^{\prime\prime}}}{W}\right)_{i}\geq\left(C\cdot\frac{\hat{x}^{t_{i}+\delta}}{W}\right)_{i}\geq
1\geq 1-\epsilon/2$.

To summarize, we have the following guarantee for every constraint $i\in[m]$
at the start of round $t^{\prime\prime}$.

$\left(C\cdot\frac{\hat{x}^{t^{\prime\prime}}}{W}\right)_{i}\geq
1-\epsilon/2.$ (2.7)

Since no new phase got initiated just before round $t^{\prime\prime}$ (see
steps (10) – (11) in Figure 3), we infer that
$\left\lVert\hat{x}^{t^{\prime\prime}}\right\rVert_{1}\leq(1-\epsilon/2)^{-1}\cdot
W$. Thus, from (2.7), we get the following guarantee for every constraint
$i\in[m]$.

$\left(C\cdot
x^{t^{\prime\prime}}\right)_{i}\geq\left(C\cdot\frac{\hat{x}^{t^{\prime\prime}}}{W}\right)_{i}\cdot(1-\epsilon/2)\geq(1-\epsilon/2)^{2}\geq
1-\epsilon,\text{ where
}x^{t^{\prime\prime}}:=\frac{\hat{x}^{t^{\prime\prime}}}{W}.$ (2.8)

In other words, the vector $x^{t^{\prime\prime}}$ satisfies the inequality
$C\cdot x^{t^{\prime\prime}}\geq(1-\epsilon)\cdot\mathbb{1}$, and hence the
decision to return $x^{t^{\prime\prime}}$ as a solution to the covering LP is
also consistent with the template described in Figure 1. ∎

######  Theorem 2.6.

The procedure in Figure 3 either returns an $x^{t}\in\mathbb{R}_{\geq 0}^{n}$
with $\mathbb{1}^{\top}x^{t}=1$ and $Cx^{t}\geq(1-\epsilon)\cdot\mathbb{1}$,
or it returns a $y\in\mathbb{R}_{\geq 0}^{m}$ with $\mathbb{1}^{\top}y=1$ and
$C^{\top}y\leq(1+4\epsilon)\cdot\mathbb{1}$.

###### Proof.

Follows from Theorem 2.3 and Lemma 2.5. ∎

It now remains to bound the running time of this algorithm. Towards this end,
the lemma below analyzes the time taken by a call to the subroutine Step-
size$(i,\hat{x}^{t},W)$.

######  Lemma 2.7.

A call to Step-size$(i,t,\hat{x}^{t},W)$ can be implemented in
$O\left(N_{i}\cdot\log^{2}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)$
time, where $N_{i}$ is the number of non-zero entries in row $i\in[m]$ of the
matrix $C\in[0,\lambda]^{m\times n}$.

###### Proof.

It takes $O(N_{i}\cdot\log\kappa)$ time to compute
$\left(C\cdot\frac{z^{\kappa}}{W}\right)_{i}$ for any $\kappa\geq 1$ (see step
(1) of Figure 5). Furthermore, the value of
$\left(C\cdot\frac{z^{\kappa}}{W}\right)_{i}$ can only increase as we increase
$\kappa$. Thus, we can find $\delta$, as in steps (2) - (5) of Figure 5, by
doing a binary search in $O(N_{i}\cdot\log T\cdot\log T)$ time. The lemma
follows since $T=\lambda\ln(n)/\epsilon^{2}$. ∎

The next lemma bounds the time taken to enforce a constraint.

######  Lemma 2.8.

A call to Enforce$(i,t,\hat{x}^{t},W)$ can be implemented in
$O\left(N_{i}\cdot\log^{2}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)$
time, where $N_{i}$ is the number of non-zero entries in row $i\in[m]$ of the
matrix $C\in[0,\lambda]^{m\times n}$.

###### Proof.

The key idea is that we do not need to explicitly store all the vectors
$\hat{x}^{t+1},\ldots,\hat{x}^{t+\delta}$ and $y^{t},\ldots,y^{t+\delta-1}$.
Instead, using standard data structures, the overall algorithm (outlined in
Figure 3) keeps track of only the following information corresponding to a
specific call to Enforce$(i,t,\hat{x}^{t},W)$.

(1) The value of $t$ at the start of the call, and the step-size $\delta$
computed by the call.

(2) The index $i\in[m]$ corresponding to the call. This index implicitly
defines all the vectors $y^{t},\ldots,y^{t+\delta-1}$.

(3) A vector $\hat{x}\in\mathbb{R}_{\geq 0}^{n}$, which was equal to
$\hat{x}^{t}$ just before the call, and needs to be set to
$\hat{x}^{t+\delta}$ at the end of the call. This will be required to
implement the next iteration of the For loop in Figure 3.

The overall algorithm (in Figure 3) can easily recover the answer it needs to
return, provided it keeps track of the above mentioned pieces of information
corresponding to each call to the Enforce subroutine.

Thus, the runtime of a call to Enforce$(i,t,\hat{x}^{t},W)$ is dominated by
the time spent on the following two tasks: (1) computing the value of
$\delta$, and (2) ensuring that the vector $\hat{x}$, which was equal to
$\hat{x}^{t}$ just before the call, equals $\hat{x}^{t+\delta}$ at the end of
the call. The time needed for the former task is bounded by Lemma 2.7, whereas
the time needed for the latter task is $O(N_{i}\cdot\log\delta)$. The lemma
follows since $\delta\leq T=\frac{\lambda\ln(n)}{\epsilon^{2}}$. ∎

We next bound the total number of phases in the algorithm.

######  Lemma 2.9.

Throughout the duration of the algorithm outlined in Figure 3, we have:
$\left\lVert\hat{x}^{t}\right\rVert_{1}\leq n^{(1/\epsilon)}$.

###### Proof.

Consider any round $t\in[T]$, which corresponds to an iteration of the For
loop in Figure 1 (see Lemma 2.5). Observe that:

$\displaystyle\left\lVert\hat{x}^{t+1}\right\rVert_{1}-\left\lVert\hat{x}^{t}\right\rVert_{1}=\sum_{j\in[n]}\left(\left(\hat{x}^{t+1}\right)_{j}-\left(\hat{x}^{t}\right)_{j}\right)=\sum_{j\in[n]}\left(\hat{x}^{t}\right)_{j}\cdot\left(\epsilon\cdot\frac{C_{i_{t},j}}{\lambda}\right)=\frac{\epsilon}{\lambda}\cdot\left(C\hat{x}^{t}\right)_{i_{t}}<\frac{\epsilon}{\lambda}\cdot\left\lVert\hat{x}^{t}\right\rVert_{1}.$

The last inequality follows since $\left(Cx^{t}\right)_{i_{t}}<1$ and
$x^{t}:=\hat{x}^{t}/\left\lVert\hat{x}^{t}\right\rVert_{1}$. Rearranging the
terms, we get:

$\left\lVert\hat{x}^{t+1}\right\rVert_{1}\leq\left(1+\frac{\epsilon}{\lambda}\right)\cdot\left\lVert\hat{x}^{t}\right\rVert_{1}.$
(2.9)

As $T=\frac{\lambda\ln(n)}{\epsilon^{2}}$ and
$\left\lVert\hat{x}^{0}\right\rVert_{1}=n$, from (2.9) we get:
$\left\lVert\hat{x}^{t}\right\rVert_{1}\leq\left(1+\frac{\epsilon}{\lambda}\right)^{T}\cdot\left\lVert\hat{x}^{0}\right\rVert_{1}\leq
n^{(1/\epsilon)}$ for all $t\in[T]$. ∎

######  Corollary 2.10.

The algorithm outlined in Figure 3 has at most
$O\left(\frac{\log(n)}{\epsilon^{2}}\right)$ many phases.

###### Proof.

We initiate a new phase whenever $\left\lVert\hat{x}^{t}\right\rVert$
increases by a multiplicative factor of $(1-\epsilon/2)^{-1}$. Hence, by Lemma
2.9, the number of phases is at most
$O\left(\log_{(1-\epsilon/2)^{-1}}n^{(1/\epsilon)}\right)=O\left(\frac{\log
n}{\epsilon^{2}}\right)$. ∎

We are now ready to bound the total runtime of our algorithm.

######  Theorem 2.11.

The algorithm outlined in Figure 3 can be implemented in
$O\left(N\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{2}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)$
time, where $N$ is the total number of non-zero entries in the matrix
$C\in[0,\lambda]^{m\times n}$.

###### Proof.

Consider a given phase of the algorithm. From Lemma 2.8, it follows that the
time taken to enforce any specific constraint $i\in[m]$ in this phase is at
most
$O\left(N_{i}\cdot\log^{2}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)$.
Since each constraint gets enforced at most once during this phase, the total
time spent in this phase is at most:

$O\left(\sum_{i\in[m]}N_{i}\cdot\log^{2}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)=O\left(N\cdot\log^{2}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right).$

The theorem now follows from Corollary 2.10. ∎

###  2.2 Dynamic Whack-a-Mole MWU Algorithm for Covering LPs

In this section, we focus on designing a dynamic algorithm for Problem 2.1 in
the following setting. At preprocessing, we receive a constraint matrix
$C\in[0,\lambda]^{m\times n}$. Subsequently, the matrix $C$ undergoes a
sequence of restricting updates, where each update decreases the value of some
entry $C_{ij}$ of the matrix $C$.101010As we will see later in Section 2.5.2,
we can assume that all updates are applied only to entries of the matrix $C$
(and not on the objective nor the RHS of the constraints). Throughout this
sequence of updates, we need to maintain either a vector
$\tilde{x}\in\mathbb{R}_{\geq 0}^{n}$ with $\mathbb{1}^{\top}\tilde{x}\leq
1+\Theta(\epsilon)$ and $C\tilde{x}\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$,
or a vector $y\in\mathbb{R}_{\geq 0}^{m}$ with $\mathbb{1}^{\top}y=1$ and
$C^{\top}y\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$.

We will show that our implementation of the whack-a-mole MWU algorithm from
Section 2.1.3 seamlessly extends to this dynamic setting. In more details, our
dynamic algorithm works as follows.

Preprocessing: At preprocessing, we run the static algorithm from Section
2.1.3 on the input matrix $C$. Depending on its outcome, we consider one of
the following two cases.

Case I: The static algorithm returns a vector $y\in\mathbb{R}_{\geq 0}^{m}$,
as in step (09) of Figure 3. It follows that $\mathbb{1}^{\top}y=1$ and
$C^{\top}y\leq(1+4\epsilon)\cdot\mathbb{1}$ (see Theorem 2.6). In this case,
the vector $y$ will continue to remain an approximately feasible solution to
the dual packing LP as the matrix $C$ undergoes restricting entry updates in
future. Hence, our dynamic algorithm terminates without having to process any
update.

Case II: The static algorithm returns a vector
$x^{t}:=\hat{x}^{t}/\left\lVert\hat{x}^{t}\right\rVert_{1}$, as in step (12)
of Figure 3. It follows that $\mathbb{1}^{\top}x^{t}=1$ and
$Cx^{t}\geq(1-\epsilon)\cdot\mathbb{1}$ (see Theorem 2.6). Our dynamic
algorithm, however, will explicitly maintain only the vector
$\tilde{x}^{t}:=\hat{x}^{t}/W$, which is a very good approximation to $x^{t}$
since $W\leq\left\lVert\hat{x}^{t}\right\rVert_{1}\leq(1-\epsilon/2)^{-1}\cdot
W\leq(1+\epsilon)\cdot W$. Thus, in this case, after preprocessing our dynamic
algorithm returns a vector $\tilde{x}^{t}$ which satisfies
$\mathbb{1}^{\top}\tilde{x}^{t}\leq 1+\epsilon$ and
$C\tilde{x}^{t}\geq(1-\epsilon)\cdot\mathbb{1}$.

Handling a restricting entry update to $C$: Consider an update which decreases
the value of some entry $C_{ij}$ of the matrix $C$. To handle this update, we
simply run the steps (05) - (11) of Figure 3. In words, we observe that if any
constraint in the covering LP gets violated due to this update, then it must
be the constraint $i\in[m]$. Thus, we check whether the current solution
$\tilde{x}^{t}:=\hat{x}^{t}/W$ approximately satisfies constraint $i$. If not,
then we enforce that constraint by repeatedly whacking it. At the end of this
process, we end up in one of three possible cases. (Case 1): $W$ is no longer
an accurate estimate of $\left\lVert\hat{x}^{t}\right\rVert_{1}$. In this
case, we initiate a new phase. (Case 2): $t=T$. Here, we return an
approximately feasible solution $y$ to the dual packing LP, and we terminate
the dynamic algorithm since $y$ remains a valid dual solution after any future
update. (Case 3): If we are neither in Case 1 nor in Case 2, then we infer
that $\tilde{x}^{t}$ is now an approximately feasible solution to the covering
LP, with $\mathbb{1}^{\top}\tilde{x}^{t}\leq 1+\epsilon$ and
$C\tilde{x}^{t}\geq(1-\epsilon)\cdot\mathbb{1}$. This holds because repeatedly
whacking constraint $i$ does not lead to any other constraint being violated,
provided we remain in the same phase.

Rounds/phases: Before proceeding any further, we recall that a new round
begins whenever we whack a constraint, and the variable $t$ denotes the total
number of rounds we have seen so far. In contrast, a new phase begins whenever
$\left\lVert\hat{x}^{t}\right\rVert_{1}$ increases by a multiplicative factor
of $(1-\epsilon/2)^{-1}$.

It now remains to analyze our dynamic algorithm. We start by noting that
Theorem 2.6 and Lemma 2.9 seamlessly extend to the dynamic setting. We
respectively summarize the analogues of these statements in Theorem 2.12 and
Lemma 2.13 below. Their proofs are deferred to Appendix A.

######  Theorem 2.12.

If our dynamic algorithm returns a vector $y\in\mathbb{R}_{\geq 0}^{m}$ after
handling an update, then $\mathbb{1}^{\top}y=1$ and
$C^{\top}y\leq(1+4\epsilon)\cdot\mathbb{1}$. In contrast, if our dynamic
algorithm returns a vector $\tilde{x}^{t}:=\hat{x}^{t}/W\in\mathbb{R}_{\geq
0}^{n}$ after handling an update, then $\mathbb{1}^{\top}\tilde{x}^{t}\leq
1+\epsilon$ and $C\tilde{x}^{t}\geq(1-\epsilon)\cdot\mathbb{1}$.

######  Lemma 2.13.

Throughout the duration of our dynamic algorithm, we have
$\left\lVert\hat{x}\right\rVert^{t}_{1}\leq n^{(1/\epsilon)}$.

We now focus on bounding the total update time of our dynamic algorithm. The
key challenge here is to derive an upper bound on the maximum number of times
a given constraint $i\in[m]$ can get enforced, over the entire duration of the
algorithm.111111We say that constraint $i\in[m]$ gets enforced whenever we
call Enfore$(i,t,\hat{x}^{t},W)$. This is done in Lemma 2.14, whose proof
appears in Section 2.2.1.

######  Lemma 2.14.

Throughout the entire duration of our dynamic algorithm, a given constraint
$i\in[m]$ can get enforced at most $O\left(\frac{\log
n}{\epsilon^{2}}\cdot\log\left(\frac{\lambda\log n}{\epsilon}\right)\right)$
times.

We are now ready to bound the total update time of our dynamic algorithm.

######  Theorem 2.15.

To handle any sequence of $\tau$ restricting entry updates to $C$, our dynamic
algorithm takes
$O\left(\tau+N\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{3}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)$
time, where $N$ is the number of non-zero entries in $C$ at preprocessing.

###### Proof.

(Sketch) The total time update time is dominated by the time spent on the
following two tasks.

Task I. After an update decreases the value of some entry $C_{ij}$ of the
input matrix $C$, decide whether the constraint $i\in[m]$ is approximately
satisfied, i.e., whether
$\left(C\cdot\frac{\hat{x}^{t}}{W}\right)>1-\epsilon/2$.

Task II. Enforce a given constraint $i\in[m]$.

We first focus on bounding the total time spent on Task II. Towards this end,
we first adapt the argument in the proof of Lemma 2.8. This leads us to
conclude that whenever we enforce a constraint $i\in[m]$, it takes
$O\left(N_{i}\cdot\log^{2}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)$
time, where $N_{i}$ is the number of non-zero entries in row $i\in[m]$ of the
input matrix $C$ at preprocessing. Hence, Lemma 2.14 implies that the total
time spent on enforcing a given constraint $i\in[m]$ is at most
$O\left(N_{i}\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{3}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)$.
Summing this up over all the constraints $i\in[m]$, we infer that the total
time spent on Task II is at most:

$O\left(\sum_{i\in[m]}N_{i}\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{3}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)=O\left(N\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{3}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right).$
(2.10)

It now remains to bound the total time spent on Task I. Towards this end, we
maintain a variable $\hat{z}_{j}$ for each co-ordinate $j\in[n]$. We always
ensure that $\hat{z}_{j}=(1+\epsilon)^{\kappa}$ for some nonnegative integer
$\kappa\geq 0$. Furthermore, we ensure that $\hat{z}_{j}$ always lies within a
multiplicative $(1+\epsilon)$ factor of $\left(\hat{x}^{t}\right)_{j}$. In
other words, the value of $\hat{z}_{j}$ always forms an accurate estimate of
$\left(\hat{x}^{t}\right)_{j}$. Finally, for each constraint $i\in[m]$, we
explicitly maintain the value of $\left(C\cdot\frac{\hat{z}}{W}\right)_{i}$.
This way, we can keep track of the value of
$\left(C\cdot\frac{\hat{x}^{t}}{W}\right)_{i}$ for all $i\in[m]$, within a
multiplicative factor of $(1+\epsilon)$. This is sufficient for us to detect
whether a given constraint $i\in[m]$ is approximately satisfied, in $O(1)$
time after an update.

Fix any co-ordinate $j\in[n]$. Note that $\left(\hat{x}^{1}\right)_{j}=1$, and
by Lemma 2.13 we have
$\left(\hat{x}^{t}\right)_{j}\leq\sum_{j^{\prime}\in[n]}\left(\hat{x}^{t}\right)_{j^{\prime}}\leq
n^{(1/\epsilon)}$ for all $t\in[T]$. In words, the value of
$\left(\hat{x}^{t}\right)_{j}$ always lies in the interval
$\left[1,n^{(1/\epsilon)}\right]$. We need to update the estimate
$\hat{z}_{j}$ each time the value of $\left(\hat{x}^{t}\right)_{j}$ increases
by a multiplicative factor of $(1+\epsilon)$. Thus, throughout the duration of
our algorithm, the value of $\hat{z}_{j}$ gets updated at most
$\log_{(1+\epsilon)}n^{(1/\epsilon)}=O(\log n/\epsilon^{2})$ times.

Finally, whenever the value of $\hat{z}_{j}$ changes, we need to spend an
additional $O(N^{j})$ time to reflect this change in the values of
$\left(C\cdot\frac{\hat{z}}{W}\right)_{i}$ for all $i\in[m]$, where $N^{j}$
denotes the number of non-zero entries in column $j\in[n]$ of the matrix $C$
at preprocessing. Hence, the total time spent in this manner, in order to
maintain the estimates $\hat{z}_{j}$ and
$\left(C\cdot\frac{\hat{z}}{W}\right)_{i}$, is at most
$O\left(\sum_{j\in[n]}N^{j}\cdot(\log n/\epsilon^{2})\right)=O(N\log
n/\epsilon^{2})$. So the total time spent by our algorithm on Task I is at
most $O(\tau+N\log n/\epsilon^{2})$. The theorem now follows from (2.10). ∎

####  2.2.1 Proof of Lemma 2.14

Throughout the proof, fix a constraint $i\in[m]$. We associate a step-size
with each enforcement of this constraint. Specifically, suppose that the
constraint gets enforced in round $t$ with step-size $\delta$. Then the
constraint gets whacked $\delta$ times during this enforcement (see Figure 4).
Furthermore, note that the step-size $\delta$ lies in the range $[1,T]$,
according to Figure 5. We discretize this range $[1,T]$ into $O(\log T)$ many
intervals in powers of $2$. Armed with this discretization, we now assign an
integral rank to each enforcement of this constraint. Specifically, a given
enforcement has rank $1\leq\kappa\leq O(\log T)$ iff its step-size
$\delta\in\left[2^{\kappa-1},2^{\kappa}\right)$. We will now bound the maximum
number of enforcements of a given rank encountered by constraint $i$.

######  Claim 2.1.

Fix any integer $1\leq\kappa\leq O(\log T)$. Throughout the duration of our
dynamic algorithm, the constraint $i\in[m]$ encounters at most
$O\left(\frac{\log n}{\epsilon^{2}}\right)$ many enforcements of rank
$\kappa$.

###### Proof.

Suppose that the constraint $i\in[m]$ encounters $\gamma+1$ enforcements of
rank $\kappa$. Furthermore, suppose that these enforcements occurr in rounds
$t_{1}<t_{2}<\cdots<t_{\gamma}<t_{\gamma+1}$. We will show that $\gamma=O(\log
n/\epsilon^{2})$.

Focus on the second-last of these enforcements, that occur in round
$t_{\gamma}$. Just before this enforcement, we have
$\left(C\cdot\frac{\hat{x}^{t}}{W}\right)_{i}<1-\epsilon/2$. In contrast, just
after this enforcement, we have
$\left(C\cdot\frac{\hat{x}^{t}}{W}\right)_{i}\geq 1$.121212Here, we rely on
the fact that this is not the last enforcement of constraint $i$, for
otherwise we might execute step (3) in Figure 5. So the value of
$\left(C\cdot\frac{\hat{x}^{t}}{W}\right)_{i}$ increases by at least a
multiplicative factor of $1+\Theta(\epsilon)$ during this enforcement. Hence,
there must exist some co-ordinate $j^{*}\in[n]$ such that
$\left(\hat{x}^{t}\right)_{j^{*}}$ also increases by at least a multiplicative
factor of $1+\Theta(\epsilon)$ during the same enforcement in round
$t_{\gamma}$. On the other hand, since the concerned enforcement has rank
$\kappa$, it has a step-size of at most $2^{\kappa}$. Thus, due to this
enforcement $\left(\hat{x}^{t}\right)_{j^{*}}$ increases by at most a factor
of
$\left(1+\epsilon\cdot\frac{C_{ij^{*}}^{t_{\gamma}}}{\lambda}\right)^{2^{\kappa}}$,
where $C^{t_{\gamma}}_{ij^{*}}$ denotes the value of $C_{ij^{*}}$ just before
round $t_{\gamma}$. Accordingly, we infer that:

$\left(1+\epsilon\cdot\frac{C_{ij^{*}}^{t_{\gamma}}}{\lambda}\right)^{2^{\kappa}}\geq
1+\Theta(\epsilon).$ (2.11)

Next, consider any previous enforcement with rank $\kappa$ that occurs in some
round $t_{\gamma^{\prime}}$ (where $1\leq\gamma^{\prime}\leq\gamma$), and
focus on the same co-ordinate $j^{*}$. Since the concerned enforcement has
step-size at least $2^{\kappa-1}$, we infer that due to this enforcement
$\left(\hat{x}^{t}\right)_{j^{*}}$ increases by at least a multiplicative
factor of:

$\left(1+\epsilon\cdot\frac{C_{ij^{*}}^{t_{\gamma^{\prime}}}}{\lambda}\right)^{2^{\kappa-1}}=\sqrt{\left(1+\epsilon\cdot\frac{C_{ij^{*}}^{t_{\gamma}}}{\lambda}\right)^{2^{\kappa}}}\geq\sqrt{1+\Theta(\epsilon)}=1+\Theta(\epsilon).$

The inequality follows from (2.11). To summarize, we conclude that during each
of the enforcements in rounds $t_{1},\ldots,t_{\gamma}$, the value of
$\left(\hat{x}^{t}\right)_{j^{*}}$ increases by at least a factor of
$1+\Theta(\epsilon)$.

Finally, observe that $\left(\hat{x}^{t}\right)_{j^{*}}=1$ at the start of the
algorithm, and that the value of $\left(\hat{x}^{t}\right)_{j^{*}}$ increases
monotonically with time. Thus, at the end of the enforcement in round
$t_{\gamma}$, we have:

$\left(1+\Theta(\epsilon)\right)^{\gamma}\leq\left(\hat{x}^{t}\right)_{j^{*}}\leq\sum_{j\in[n]}\left(\hat{x}^{t}\right)_{j}\leq
n^{(1/\epsilon)}.$ (2.12)

The last inequality holds due to Lemma 2.13. From (2.12), we infer that
$\gamma=O(\log n/\epsilon^{2})$. ∎

Claim 2.1 implies that a given constraint $i\in[m]$ is enforced at most
$O\left(\frac{\log n}{\epsilon^{2}}\cdot\log T\right)$ times by our dynamic
algorithm. Lemma 2.14 now follows from the fact that
$T=\lambda\ln(n)/\epsilon^{2}$.

###  2.3 Streaming Whack-a-Mole MWU Algorithm

In this section, we focus on designing a streaming algorithm for Problem 2.1
in the following setting. We get a matrix $C\in R_{\geq 0}^{m\times n}$ as
input. The rows of $C$ are stored one after the other in a read-only
repository. We wish to design an algorithm which makes one or more passes
through this repository, and then either outputs a vector
$x\in\mathbb{R}_{\geq 0}^{n}$ with $\mathbb{1}^{\top}x=1$ and
$Cx\geq(1-\epsilon)\cdot\mathbb{1}$, or outputs a vector $y\in\mathbb{R}_{\geq
0}^{m}$ with $\mathbb{1}^{\top}y=1$ and
$C^{\top}y\leq(1+4\epsilon)\cdot\mathbb{1}$. The goal is to minimize the
number of passes and the space complexity (excluding the space taken up by the
repository to store the input) of the algorithm.

We observe that the static whack-a-mole MWU algorithm, as described in Section
2.1.3, immediately extends to this streaming setting if we allow the algorithm
to have a space complexity of $O(m+n)$. Specifically, we can implement the
main For loop in Figure 3 in a single pass as follows. The algorithm
explicitly maintains a vector $\hat{x}=\hat{x}^{t}\in\mathbb{R}_{\geq 0}^{n}$,
the values $W,t\in\mathbb{R}_{\geq 0}$, and a vector
$y^{*}=(1/T)\cdot\sum_{t^{\prime}=1}^{t}y^{t^{\prime}}\in\mathbb{R}_{\geq
0}^{m}$ in its memory. Note that when $t=T$, we have $y^{*}=y$. While making a
pass through the read-only repository, suppose that the algorithm encounters
row $i\in[m]$ of the matrix $C$. The algorithm checks whether
$\left(C\cdot\frac{\hat{x}}{W}\right)_{i}<1-\epsilon/2$, and if yes, then it
enforces the constraint $i\in[m]$. Using the vectors $\hat{x}$ and $y^{*}$,
this enforcement step can be performed without incurring any extra overhead in
the space complexity.

Since we can implement the main For loop in Figure 3 in one pass, the total
number of passes is equal to the number of phases of the whack-a-mole
algorithm. The next theorem now follows from Corollary 2.10.

######  Theorem 2.16.

Consider a streaming setting where the rows of the matrix
$C\in[0,\lambda]^{m\times n}$ arrive one after the other. Then there is a
deterministic streaming algorithm with space complexity $O(m+n)$ that makes
$O\left(\frac{\log n}{\epsilon^{2}}\right)$ many passes through this stream,
and either returns a vector $x\in\mathbb{R}_{\geq 0}^{n}$ with
$\mathbb{1}^{\top}x=1$ and $Cx\geq(1-\epsilon)\cdot\mathbb{1}$, or returns a
vector $y\in\mathbb{R}_{\geq 0}^{m}$ with $\mathbb{1}^{\top}y=1$ and
$C^{\top}y\leq(1+4\epsilon)\cdot\mathbb{1}$.

Next, note that if we are only required to return either the vector
$x\in\mathbb{R}_{\geq 0}^{n}$ or a special symbol Null (indicating that the
dual packing LP has an approximately feasible solution with objective $=1$),
then we can further reduce the space complexity of our streaming algorithm.
This holds because in such a scenario we only need to maintain the vector
$\hat{x}\in\mathbb{R}_{\geq 0}^{n}$ and the values $W,t\in\mathbb{R}_{\geq
0}$. In particular, we no longer need to maintain the vector
$y^{*}\in\mathbb{R}_{\geq 0}^{m}$ while making a pass through the read-only
repository. Instead, when we observe that $t=T$, we simply return Null. This
leads to the following corollary.

######  Corollary 2.17.

Consider a streaming setting where the rows of the matrix
$C\in[0,\lambda]^{m\times n}$ arrive one after the other. Then there is a
deterministic streaming algorithm with space complexity $O(n)$ that makes
$O\left(\frac{\log n}{\epsilon^{2}}\right)$ many passes through this stream,
and either returns a vector $x\in\mathbb{R}_{\geq 0}^{n}$ with
$\mathbb{1}^{\top}x=1$ and $Cx\geq(1-\epsilon)\cdot\mathbb{1}$, or returns
Null. In the latter case, it is guaranteed that there exists a vector
$y\in\mathbb{R}_{\geq 0}^{m}$ with $\mathbb{1}^{\top}y=1$ and
$C^{\top}y\leq(1+4\epsilon)\cdot\mathbb{1}$ (although the algorithm does not
return $y$).

###  2.4 Online Whack-a-Mole MWU Algorithm

In this section, we focus on designing an online algorithm for Problem 2.1 in
the following setting. An adversary chooses a matrix $C\in[0,\lambda]^{m\times
n}$ as input. In the beginning, the values of $n$ and $\lambda$ are public
knowledge, whereas only the adversary knows the value of $m$ and the entries
of the matrix $C$. Subsequently, the adversary reveals to us the rows of this
matrix one after another. We need to maintain a vector $x\in\mathbb{R}_{\geq
0}^{n}$ such that $\mathbb{1}^{\top}x\leq 1+\Theta(\epsilon)$ and
$Cx\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$ until a certain point in time, and
after that we need to terminate our algorithm by returning a
$y\in\mathbb{R}_{\geq 0}^{m}$ such that $\mathbb{1}^{\top}y\geq
1-\Theta(\epsilon)$ and $C^{\top}y\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$. We
incur a recourse of one each time we decrease the value of some variable
$\left(x\right)_{j},j\in[n]$. Our goal is to design an algorithm in this
online setting with as small total recourse as possible.

We observe that the dynamic whack-a-mole MWU algorithm, as described in
Section 2.2, seamlessly extends to this online setting. Thus, we maintain the
vector $\tilde{x}^{t}:=\hat{x}^{t}/W$. Whenever a new row $i\in[m]$ of the
matrix $C$ arrives, we check whether
$\left(C\cdot\frac{\hat{x}^{t}}{W}\right)<1-\epsilon/2$, and if the answer is
yes, then we enforce the corresponding constraint $i\in[m]$. The correctness
of this algorithm follows from Theorem 2.12.

We now derive an upper bound on the number of phases. Corollary 2.13 implies
that $\left\lVert\hat{x}^{t}\right\rVert_{1}\leq n^{(1/\epsilon)}$ throughout
the duration of the algorithm. Since
$\left\lVert\hat{x}^{1}\right\rVert_{1}=n$ at the start of the algorithm, and
since we initiate a new phase whenever
$\left\lVert\hat{x}^{t}\right\rVert_{1}$ increases by a multiplicative factor
of $1+\Theta(\epsilon)$, it follows that the total number of phases is at most
$\log_{(1+\Theta(\epsilon))}n^{(1/\epsilon)}=O\left(\frac{\log
n}{\epsilon^{2}}\right)$.

Next, note that within a given phase our algorithm incurs zero recourse. This
holds because the values $\left(\hat{x}^{t}/W\right)_{j}$ can only increase
when we enforce a constraint within the phase (as $W$ does not change). On the
other hand, we incur a recourse of $n$ each time we initiate a new phase,
since we have $n$ variables and each of these variables decreases its value as
we increase $W$ at the start of the phase. Hence, the total recourse of the
algorithm is $n$ times the number of phases. This leads to the following
theorem.

######  Theorem 2.18.

Consider an online setting where the rows of the matrix
$C\in[0,\lambda]^{m\times n}$ arrive one after another. Let $N$ denote the
number of non-zero entries in $C$. There is a deterministic online algorithm
with total recourse $O\left(\frac{n\log n}{\epsilon^{2}}\right)$ which has the
following property. It maintains a vector $x\in\mathbb{R}_{\geq 0}^{n}$ with
$\mathbb{1}^{\top}x\leq 1+\Theta(\epsilon)$ and
$Cx\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$ until a certain point in time, and
after that it terminates and returns a vector $y\in\mathbb{R}_{\geq 0}^{m}$
with $\mathbb{1}^{\top}y\geq 1-\Theta(\epsilon)$ and
$C^{\top}y\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$.

###  2.5 Reductions to General Packing-Covering LPs

Consider a matrix $C\in\mathbb{R}_{\geq 0}^{m\times n}$, vectors
$a\in\mathbb{R}_{>0}^{n}$, $b\in\mathbb{R}_{>0}^{m}$, and a generic covering
LP defined below.

$\displaystyle\text{Minimise }a^{\top}x$ $\displaystyle\text{ s.t. }Cx\geq
b\text{ and }x\in\mathbb{R}_{\geq 0}^{n}.$ (2.13)

The dual of the above LP is given by:

$\displaystyle\text{Maximise }b^{\top}y$ $\displaystyle\text{ s.t.
}C^{\top}y\leq a\text{ and }y\in\mathbb{R}_{\geq 0}^{m}.$ (2.14)

Let Opt be the optimal objective value of this pair of primal and dual LPs.
Say that $x\in\mathbb{R}_{\geq 0}^{n}$ is an $\epsilon$-approximate optimal
solution to LP (2.13) iff $a^{\top}x\leq(1+\Theta(\epsilon))\cdot\text{{\sc
Opt}}$ and $Cx\geq(1-\Theta(\epsilon))\cdot b$. Similarly, say that
$y\in\mathbb{R}_{\geq 0}^{m}$ is an $\epsilon$-approximate optimal solution to
LP (2.14) iff $b^{\top}y\geq(1-\Theta(\epsilon))\cdot\text{{\sc Opt}}$ and
$C^{\top}y\leq(1+\Theta(\epsilon))\cdot a$.131313This notion of an
$\epsilon$-approximation is equivalent to the one defined at the start of
Section 1, upto a multiplicative factor of $1+\Theta(\epsilon)$. To see why
this is true, consider an $x$ such that
$1^{\top}x\leq(1+\Theta(\epsilon))\cdot\text{{\sc Opt}}$ and
$Cx\geq(1-\Theta(\epsilon))\cdot b$. Then it follows that
$1^{\top}\tilde{x}\leq(1+\Theta(\epsilon))\cdot\text{{\sc Opt}}$ and
$C\tilde{x}\geq b$, where $\tilde{x}:=\frac{x}{1-\Theta(\epsilon)}$. A similar
argument holds for an $\epsilon$-approximation to LP (2.14). We will now
explain how to use the whack-a-mole MWU algorithm to obtain
$\epsilon$-approximate optimal solutions to this pair of LPs in static,
dynamic, streaming and online settings.

Specifically, we describe how an algorithm for Problem 2.1 can be used in a
black-box manner to solve general packing-covering LPs. Such a reduction works
by first guessing the value of Opt, and then showing an equivalence between:
(a) finding a solution with objective $=\text{{\sc Opt}}$ and (b) solving
Problem 2.1. The equivalence follows from standard scaling techniques.

####  2.5.1 Static Setting

In this section, we show how to prove the following theorem.

######  Theorem 2.19.

There is a deterministic $\epsilon$-approximation algorithm for solving LP
(2.13) that runs in
$O\left(N\cdot\frac{\log(n)}{\epsilon^{3}}\cdot\log^{2}\left(\frac{nU\log(n)}{\epsilon
L}\right)\cdot\log(nU/L)\right)$ time. Here, $N$ denotes the number of non-
zero entries in $C$, whereas $L$ (resp. $U$) respectively denotes a lower
(resp. upper) bound on the minimum (resp. maximum) value of any non-zero entry
in $C,a,b$. The same guarantee also holds for solving LP (2.14).

Define a matrix $C^{\prime}\in\mathbb{R}_{\geq 0}^{m\times n}$ such that
$C^{\prime}_{ij}:=C_{ij}/(a_{j}b_{i})$ for all $i\in[m],j\in[n]$. It is easy
to check that LP (2.13) and LP (2.14) can be equivalently written as:

$\displaystyle\text{Minimise }\mathbb{1}^{\top}x$ $\displaystyle\text{ s.t.
}C^{\prime}x\geq\mathbb{1}\text{ and }x\in\mathbb{R}_{\geq 0}^{n}.$ (2.15)
$\displaystyle\text{Maximise }\mathbb{1}^{\top}y$ $\displaystyle\text{ s.t.
}(C^{\prime})^{\top}y\leq\mathbb{1}\text{ and }y\in\mathbb{R}_{\geq 0}^{m}.$
(2.16)

We can compute the matrix $C^{\prime}$ in $O(N)$ time. Furthermore, the
maximum (resp. minimum) value of any non-zero entry of $C^{\prime}$ is upper
(resp. lower) bounded by $U/L^{2}$ (resp. $L/U^{2}$). Let Opt denote the
optimal objective value of LP (2.15) and LP (2.16). Note that
$L^{2}/U\leq\text{{\sc Opt}}\leq nU^{2}/L$. We discretize this range
$[L^{2}/U,nU^{2}/L]$ in powers of $(1+\epsilon)$, to obtain
$\log_{(1+\epsilon)}(nU^{3}/L^{3})=\Theta(\log(nU/L)/\epsilon)$ many guesses
for Opt. For each such guess $\mu$, we consider the following problem.

######  Problem 2.20.

Either return an $x\in\mathbb{R}_{\geq 0}^{n}$ such that
$\mathbb{1}^{\top}x\leq(1+\Theta(\epsilon))\cdot\mu$ and
$C^{\prime}x\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$, or return a
$y\in\mathbb{R}_{\geq 0}^{m}$ such that
$\mathbb{1}^{\top}y\geq(1-\Theta(\epsilon))\cdot\mu$ and
$(C^{\prime})^{\top}y\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$.

Next, define a matrix $C^{\prime\prime}\in\mathbb{R}_{\geq 0}^{m\times n}$
where $C^{\prime\prime}_{ij}:=\mu\cdot C_{ij}$ for all $i\in[m],j\in[n]$, and
observe that Problem 2.20 is equivalent to the following problem.

######  Problem 2.21.

Either return an $x\in\mathbb{R}_{\geq 0}^{n}$ such that
$\mathbb{1}^{\top}x\leq 1+\Theta(\epsilon)$ and
$C^{\prime\prime}x\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$, or return a
$y\in\mathbb{R}_{\geq 0}^{m}$ such that $\mathbb{1}^{\top}y\geq
1-\Theta(\epsilon)$ and
$(C^{\prime\prime})^{\top}y\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$.

Note that $C^{\prime\prime}\in[0,\lambda]^{m\times n}$ where
$\lambda=\mu\cdot(U/L^{2})\leq nU^{3}/L^{3}$. Accordingly, we can solve
Problem 2.21 by using our whack-a-mole MWU algorithm from Section 2.1.
According to Theorem 2.11, this takes
$O\left(N\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{2}\left(\frac{nU^{3}\log(n)}{\epsilon
L^{3}}\right)\right)=O\left(N\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{2}\left(\frac{nU\log(n)}{\epsilon
L}\right)\right)$ time.

It is easy to check that we can recover $\epsilon$-approximate optimal
solutions to LP (2.13) and LP (2.14) if we solve Problem 2.21 for each of the
$\Theta(\log(nU/L)/\epsilon)$ many guesses $\mu$. This leads us to Theorem
2.19.

####  2.5.2 Dynamic Setting

In this section, we show how to prove the following theorem.

######  Theorem 2.22.

Consider any sequence of $\tau$ restricting updates to LP (2.13), where each
update either decreases an entry of $C$, or increases an entry of $a,b$. Let
$N$ denote the total number of non-zero entries in $C$ at preprocessing. Let
$L$ (resp. $U$) denote a lower (resp. upper) bound on the minimum (resp.
maximum) value of a non-zero entry of $C,a,b$. We can deterministically
maintain an $\epsilon$-approximate optimal solution to LP (2.13) in
$O\left(\tau\cdot\frac{\log(nU/L)}{\epsilon}+N\cdot\frac{\log(n)}{\epsilon^{3}}\cdot\log^{3}\left(\frac{nU\log(n)}{\epsilon
L}\right)\cdot\log(nU/L)\right)$ total time. The same guarantee also holds for
maintaining an $\epsilon$-approximate solution to LP (2.14), which undergoes
relaxing updates.

As in Section 2.5.1, we make $\Theta(\log(nU/L)/\epsilon)$ many guesses for
Opt. For each such guess $\mu$, we maintain a solution to Problem 2.20, which,
in turn, is equivalent to Problem 2.21. This allows us to maintain
$\epsilon$-approximate optimal solutions to LP (2.13) and LP (2.14) in the
dynamic setting.

Fix any guess $\mu$, and focus on the corresponding instance of Problem 2.21.
Since we are satisfied with an $\epsilon$-approximate optimal solution, we can
safely assume that any update with a meaningful impact on the solution changes
the corresponding entry by at least a multiplicative factor of $(1+\epsilon)$.
Henceforth, we only focus on handling these meaningful updates. Note that each
entry of $C,a,b$ participates in at most
$\log_{(1+\epsilon)}(U/L)=O\left(\frac{\log(U/L)}{\epsilon}\right)$ many
meaningful updates. Furthermore, each time there is a meaningful restricting
update to some $b_{i}$, it leads to at most $O(N_{i})$ many restricting entry
updates to the matrix $C^{\prime\prime}$, where $N_{i}$ is the number of non-
zero entries in the $i^{th}$ row of $C$ at preprocessing. Similarly, whenever
there is a meaningful restricting update to some $a_{j}$, it leads to at most
$O(N^{j})$ many restricting entry updates to the matrix $C^{\prime\prime}$,
where $N^{j}$ is the number of non-zero entries in the $j^{th}$ column of $C$
at preprocessing.

Consider any sequence of $\tau$ restricting updates to LP (2.13). By the above
discussion, this leads to at most
$\tau+\left(\sum_{j\in[n]}N^{j}+\sum_{i\in[m]}N_{i}\right)\cdot
O\left(\frac{\log(U/L)}{\epsilon}\right)=\tau+O\left(N\cdot\frac{\log(U/L)}{\epsilon}\right)$
many restricting entry updates in Problem 2.21, which we solve using the
algorithm from Section 2.2. As $\lambda\leq nU^{3}/L^{3}$, Theorem 2.15
implies a total update time of:

$O\left(\tau+N\cdot\frac{\log(U/L)}{\epsilon}+N\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{3}\left(\frac{\lambda\log(n)}{\epsilon}\right)\right)=O\left(\tau+N\cdot\frac{\log(n)}{\epsilon^{2}}\cdot\log^{3}\left(\frac{nU\log(n)}{\epsilon
L}\right)\right).$

Theorem 2.22 follows since we run
$\Theta\left(\frac{\log(nU/L)}{\epsilon}\right)$ copies of the dynamic
algorithm, one for each $\mu$.

####  2.5.3 Streaming Setting

In this section, we consider the streaming setting where the rows of the
constraint matrix of a covering LP (or equivalently, the columns of the
constraint matrix of the dual packing LP) are arriving one after another. We
show how to prove the following two theorems.

######  Theorem 2.23.

Consider a streaming setting where the columns of the constraint matrix of LP
(2.14) arrive one after another. There is a deterministic algorithm with space
complexity $O(m+n)$ that makes $O\left(\frac{\log
n\cdot\log(nU/L)}{\epsilon^{3}}\right)$ passes through the stream, and returns
an $\epsilon$-approximate optimal solution to LP (2.14). Here, $L$ (resp. $U$)
denotes a lower (resp. upper) bound on the value of any non-zero entry of
$C,a,b$.

######  Theorem 2.24.

Consider a streaming setting where the rows of the constraint matrix of LP
(2.13) arrive one after another. There is a deterministic algorithm with space
complexity $O(n)$ that makes $O\left(\frac{\log
n\cdot\log(nU/L)}{\epsilon^{3}}\right)$ passes through the stream, and returns
an $\epsilon$-approximate optimal solution to LP (2.13). Here, $L$ (resp. $U$)
denotes a lower (resp. upper) bound on the value of any non-zero entry of
$C,a,b$.

As in Section 2.5.1, we make $\Theta(\log(nU/L)/\epsilon)$ many guesses for
Opt. For each such guess $\mu$, we solve Problem 2.20 in the streaming
setting, which, in turn, is equivalent to Problem 2.21. This allows us to
return $\epsilon$-approximate optimal solutions to LP (2.13) and LP (2.14).

Fix any guess $\mu$, and focus on the corresponding instance of Problem 2.21.
Suppose that we are allowed to have a space complexity of $O(m+n)$. By Theorem
2.16, we can solve Problem 2.21 by making $O(\frac{\log n}{\epsilon^{2}})$
many passes through the stream. Theorem 2.23 now follows since we need to
solve Problem 2.21 for each guess $\mu$, which increases the number of passes
by a multiplicative factor of $\Theta(\log(nU/L)/\epsilon)$.

Finally, Theorem 2.24 follows if we apply the same strategy described above
and use Corollary 2.17.

####  2.5.4 Online Setting

In this section, we explain how to prove the following theorem.

######  Theorem 2.25.

Consider an online setting where the constraints of LP (2.13) arrive one after
another. There is a deterministic algorithm which maintains an
$\epsilon$-approximate optimal solution to this LP with total recourse
$O\left(n\cdot\frac{\log
n}{\epsilon^{3}}\cdot\log\left(\frac{nU}{L}\right)\right)$. Here, $L$ (resp.
$U$) is a lower (resp. upper) bound on the value of any non-zero entry of
$C,a,b$.

As in Section 2.5.1, we make $\Theta(\log(nU/L)/\epsilon)$ many guesses for
Opt. For each such guess $\mu$, we solve Problem 2.20 in the online setting,
which, in turn, is equivalent to Problem 2.21. This allows us to maintain an
$\epsilon$-approximate optimal solutions to LP (2.13). Theorem 2.25 now
follows from Theorem 2.18 as the total recourse increases by a multiplicative
factor of $\Theta(\log(nU/L)/\epsilon)$.

###  2.6 Challenges for Dynamic Whack-a-Mole MWU Algorithm for Packing LPs

We have so far focussed on the whack-a-mole MWU algorithm for covering LPs.
For packing LPs, there exists an analogous whack-a-mole MWU algorithm. To see
this, consider the following problem.

######  Problem 2.26.

Given a matrix $P\in[0,\lambda]^{m\times n}$ where $\lambda>0$, either return
an $x\in\mathbb{R}_{\geq 0}^{n}$ with $\mathbb{1}^{\top}x\geq
1-\Theta(\epsilon)$ and $Px\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$, or return
a $y\in\mathbb{R}_{\geq 0}^{m}$ with $\mathbb{1}^{\top}y\leq
1+\Theta(\epsilon)$ and $P^{\top}y\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$.

The basic template for a whack-a-mole algorithm for Problem 2.26 is described
in Figure 6 and Figure 7. Note that this is completely analogous to the
template in Section 2.1.1.

01. Define $T\leftarrow\frac{\lambda\ln(n)}{\epsilon^{2}}$, and two vectors $\hat{x}^{1},x^{1}\in\mathbb{R}_{\geq 0}^{n}$ where $\hat{x}^{1}\leftarrow\mathbb{1}$ and $x^{1}\leftarrow\frac{\hat{x}^{1}}{\left\lVert\hat{x}^{1}\right\rVert_{1}}$. 02. For $t=1$ to $T$: 03. Either 04. Conclude that $\left(P\cdot x^{t}\right)_{i}\leq 1+\epsilon$ for all $i\in[m]$. 05. Terminate the For loop, and Return $(x^{t},\text{{\sc Null}})$. 06. Or 07. Find a packing constraint $i_{t}\in[m]$ such that $\left(P\cdot x^{t}\right)_{i_{t}}>1$. 08. $\hat{x}^{t+1}\leftarrow\text{\sc{Whack}}(i_{t},\hat{x}^{t})$. // See Figure 7. 09. $x^{t+1}\leftarrow\frac{\hat{x}^{t+1}}{\left\lVert\hat{x}^{t+1}\right\rVert_{1}}$. 10. Let $y^{t}\in\Delta^{m}$ be the vector where $\left(y^{t}\right)_{i_{t}}=1$ and $\left(y^{t}\right)_{i}=0$ for all $i\in[m]\setminus\\{i_{t}\\}$. 11. $y\leftarrow(1/T)\cdot\sum_{t=1}^{T}y^{t}$. 12. Return $(\text{{\sc Null}},y)$.

Figure 6:  The Whack-a-Mole MWU Algorithm for a Packing LP.

1. For all $j\in[n]$: 2. $\hat{z}_{j}\leftarrow\left(1-\epsilon\cdot\frac{P_{ij}}{\lambda}\right)\cdot\hat{x}_{j}$. 3. Return $\hat{z}$

Figure 7:  Whack$(i,\hat{x})$.

The key point to note is that unlike in Section 2.1.1, here the weight
$\left(\hat{x}^{t}\right)_{j}$ of an expert $j\in[n]$ (see the discussion in
the beginning of Section 2.1.2) can only decrease whenever we whack a
constraint. Nevertheless, we can easily extend the analysis from Section 2.1.1
to obtain the following theorem.

######  Theorem 2.27.

The algorithm in Figure 6 either returns a vector $x^{t}\in\mathbb{R}_{\geq
0}^{n}$ with $\mathbb{1}^{\top}x^{t}=1$ and
$Px^{t}\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$, or it returns a vector
$y\in\mathbb{R}_{\geq 0}^{m}$ with $\mathbb{1}^{\top}y=1$ and
$P^{\top}y\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$.

From this basic template, it is straightforward to obtain a near-linear time
static algorithm for Problem 2.26. The framework also seamlessly extends to
give us whack-a-mole MWU algorithms for packing LPs in the streaming and
online settings. Thus, every theorem derived in Sections 2.5.1, 2.5.3 and
2.5.4 holds even if we switch the occurrences of LP (2.13) with that of LP
(2.14) in the concerned theorem statement. The only exception is the theorem
derived in Section 2.5.2. Below, we highlight the main challenge in obtaining
a dynamic whack-a-mole MWU algorithm for packing LPs under restricting
updates.

Recall that a key part of the analysis in Section 2.2 was deriving an upper
bound on the number of times a given constraint can get enforced throughout
the duration of the algorithm (see Lemma 2.14). The proof of Lemma 2.14, on
the other hand, relied on the property that the weight
$\left(\hat{x}^{t}\right)_{j}$ of every expert $j\in[n]$ is monotonically non-
decreasing with time and always lies in the range
$\left[1,n^{(1/\epsilon)}\right]$, and hence is polynomially bounded (see the
discussion leading to (2.12)). This property followed from three observations:
(1) at the start of the algorithm we have $\left(\hat{x}^{1}\right)_{j}=1$,
(2) the total weight $\sum_{j^{\prime}\in[n]}\left(\hat{x}^{t}\right)_{j}$ of
all the experts is at most $n^{(1/\epsilon)}$, and (3) the weight
$\left(\hat{x}^{t}\right)_{j}$ of a given expert $j\in[n]$ is at most the
total weight $\sum_{j^{\prime}\in[n]}\left(\hat{x}^{t}\right)_{j}$.

Coming back to our current setting, recall that the weight
$\left(\hat{x}^{t}\right)_{j}$ of an expert $j\in[n]$ can only decrease over
time when we run the whack-a-mole MWU algorithm on a packing LP. Thus, in
order to bound the maximum number of times a constraint can get enforced, we
need to show that the weight $\left(\hat{x}^{t}\right)_{j}$ of every expert
$j\in[n]$ lies in the range
$\left[\frac{1}{n^{\text{poly}(1/\epsilon)}},1\right]$ throughout the duration
of the algorithm. A natural way to replicate the argument from the previous
paragraph to our current setting would be to make the following sequence of
claims: (a) at the start of the algorithm we have
$\left(\hat{x}^{1}\right)_{j}=1$, (b) the total weight
$\sum_{j^{\prime}\in[n]}\left(\hat{x}^{t}\right)_{j}$ of all the experts is at
least $n^{(1/\epsilon)}$, and (c) the weight $\left(\hat{x}^{t}\right)_{j}$ of
a given expert $j\in[n]$ is at least the total weight
$\sum_{j^{\prime}\in[n]}\left(\hat{x}^{t}\right)_{j}$. Now, the crucial
observation is that although we can extend the analysis of the whack-a-mole
MWU algorithm for covering LP to prove claims (a) and (b), claim (c) clearly
does not hold for obvious reasons. Indeed, if we consider a natural extension
of the static whack-a-mole MWU algorithm for packing LPs to a setting with
restricting updates, then we can not ensure that the weight
$\left(\hat{x}^{t}\right)_{j}$ of an expert $j\in[n]$ remains polynomially
bounded. This, in turn, implies that we cannot upper bound the maximum number
of times a constraint gets enforced, and hence we cannot bound the total
update time of the algorithm.

We address this issue in Section 3, where we present an efficient dynamic
algorithm for maintaining an $\epsilon$-approximate solution to a positive LP
under relaxing updates. Section 3.3 shows that as a simple corollary of this
result, we obtain an efficient dynamic algorithm for maintaining an
$\epsilon$-approximate optimal solution to a packing (resp. covering) LP under
restricting (resp. relaxing) updates (see Theorem 3.15).

##  3 The Greedy MWU Algorithm

In this section we focus on _positive_ LPs, which are defined as follows:

$\text{Find }x\in\mathbb{R}_{\geq 0}^{n}\text{ such that }Px\leq a\text{ and
}Cx\geq b,\text{ where }P\in\mathbb{R}_{\geq 0}^{m_{p}\times
n},a\in\mathbb{R}_{\geq 0}^{m_{p}},C\in\mathbb{R}_{\geq 0}^{m_{c}\times
n},b\in\mathbb{R}_{\geq 0}^{m_{c}}.$ (3.1)

An $\epsilon$-approximate solution for the positive LP is either an
$x\in\mathbb{R}_{\geq 0}^{n}$ satisfying $Px\leq(1+\epsilon)a\text{ and
}Cx\geq(1-\epsilon)b$, or a symbol $\bot$ indicating that the LP is
infeasible. In the dynamic setting, an update to the LP can change an entry of
$P,a,C$ or $b$. Observe that the update is relaxing if it increases an entry
of $C$ or $a$, or decreases an entry of $P$ or $b$. In this section, we wish
to design a dynamic algorithm for maintaining an $\epsilon$-approximation
solution to a positive LP undergoing relaxing updates. Note that such an
algorithm will work as follows. Initially, it will return $\bot$ for a
sequence of relaxing updates. After that, at a certain point in time it will
return an $x\in\mathbb{R}_{\geq 0}^{n}$ satisfying $Px\leq(1+\epsilon)a\text{
and }Cx\geq(1-\epsilon)b$. From this point onward, the same $x$ will continue
to remain an $\epsilon$-approximate solution to the input positive LP after
every future update.

Notation and preliminaries. We now introduce a few key notations and concepts
that will be used throughout the rest of Section 3.141414We emphasize that
some of these notations are different from the ones used in Section 2. We
classify a relaxing update as an entry update if it changes an entry of $P$ or
$C$, whereas we classify a relaxing update as a translation update if it
changes an entry of $a$ or $b$. Throughout the sequence of updates, let $L$
(resp. $U$) respectively denote an upper (resp, lower) bound on the value of
any nonzero entry in $P,C,a,b$; and let $N$ denote an upper bound on the total
number of nonzero entries in $P,C$. We assume that
$U/L=O(\text{poly}(m_{p}+m_{c}+n))$, where $m_{p},m_{c}$ and $n$ respectively
denote the number of rows in $P$, the number of rows in $C$, and the number of
variables. We refer to $Px\leq a$ as the packing constraints, and we refer to
$Cx\geq b$ as the covering constraints. For all $i\in[m_{p}]$ and $k\in[n]$,
we let $P(i,k)\in\mathbb{R}_{\geq 0}$ denote the entry in the $i^{th}$ row and
$k^{th}$ column of the matrix $P$. Furthermore, we let
$P_{i}\in\mathbb{R}_{\geq 0}^{1\times n}$ denote the $i^{th}$ row of the
matrix $P$. We analogously define the notations $C(j,k)\in\mathbb{R}_{\geq 0}$
and $C_{j}\in\mathbb{R}_{\geq 0}^{1\times n}$, for all $j\in[m_{c}]$ and
$k\in[n]$. Finally, we use the symbol $v_{i}$ to denote the $i^{th}$ co-
ordinate of a vector $v=(v_{1},\ldots,v_{m})\in\mathbb{R}^{m}$.

Our main result is summarised below. In this section, we present a high level
overview of the main ideas behind the proof of Theorem 3.1. The full details
are deferred to Appendix B and Appendix C.

######  Theorem 3.1.

We can maintain an $\epsilon$-approximate solution to a positive LP undergoing
a sequence of $t>0$ relaxing updates in
$O\left(N\cdot\frac{\log^{2}(m_{c}+m_{p}+U/L)}{\epsilon^{2}}+t\right)$ total
update time.

A simplifying assumption: To convey the main ideas behind our algorithm, in
this section we focus on the setting where all the relaxing updates made to
the input LP are entry updates, for the following reason.

Consider an input positive LP $(P,C,a,b)$, which asks us to find an $x$ such
that $Px\leq a$ and $Cx\geq b$. Since we are happy with a
$\Theta(\epsilon)$-approximate solution to the input LP, we can keep ignoring
the relaxing translation updates to a packing constraint $(Px)_{i}\leq a_{i}$
(resp. covering constraint $(Cx)_{j}\geq b_{j}$) as long as $a_{i}$ (resp.
$b_{j}$) does not increase (resp. decrease) by more than a multiplicative
factor of $(1+\epsilon)$. Thus, during the course of our algorithm, a given
packing or covering constraint will essentially go through at most
$\kappa=O(\log_{(1+\epsilon)}(U/L))$ many relaxing translation updates.

Next, note that we can simulate a relaxing translation update to a packing
constraint $(Px)_{i}\leq a_{i}$ (resp. covering constraint $(Cx)_{j}\geq
b_{j}$) by making $nzp_{(i)}$ (resp. $nzc_{(j)}$) many relaxing entry updates,
where $nzp_{(i)}$ (resp. $nzc_{(j)}$) denotes the current number of nonzero
entries in row $i$ (resp. row $j$) of $P$ (resp. $C$). This is because of the
following reason: If the translation update asks us to scale up (resp. scale
down) the value of $a_{i}$ (resp. $b_{j}$) by a multiplicative factor of
$\alpha\geq 1$, then we can implement this update by scaling down (resp.
scaling up) every nonzero entry in row $i$ (resp. row $j$) of $P$ (resp. $C$)
by the same factor $\alpha$.

It follows that all the relaxing translation updates encountered by an
algorithm for this problem can be simulated by at most $\kappa N$ many
relaxing entry updates. Hence, if we prove Theorem 3.1 for relaxing entry
updates, then we can immediately convert it into an algorithm that handles
both translation and entry updates with total update time
$O\left(N\cdot\frac{\log^{2}(m_{c}+m_{p}+U/L)}{\epsilon^{2}}+t+\kappa
N\right)=O\left(N\cdot\frac{\log^{2}(m_{c}+m_{p}+U/L)}{\epsilon^{2}}+t\right)$.

Accordingly, for the rest of Section 3, the phrase relaxing update will refer
to a relaxing entry update.

Scaling the constraints: Since we have to deal with only the entry updates in
this section, for notational convenience we will scale the right hand sides of
all the packing and covering constraints to $1$. Accordingly, throughout the
rest of Section 3 the input positive LP will be given by an ordered pair
$(P,C)$, where $P\in\mathbb{R}_{\geq 0}^{m_{p}\times n}$ and
$C\in\mathbb{R}_{\geq 0}^{m_{c}\times n}$ and it asks us to find an
$x\in\mathbb{R}_{\geq 0}^{n}$ such that $Px\leq 1$ and $Cx\geq 1$.

Organisation: In Section 3.1, we recap a known static greedy MWU algorithm for
positive LPs [Qua20, You14]. We present and analyse our dynamic algorithm in
Section 3.2. Finally, we show that the analysis in Section 3.2 implies a
dynamic algorithm for solving a packing (resp. covering) LP under restricting
(resp. relaxing) updates. This observation is summarized in Section 3.3.

###  3.1 Static Greedy MWU Algorithm [Qua20, You14]

Define two functions $f_{p}(x)$ and $f_{c}(x)$, which respectively correspond
to the soft-max of the packing constraints and the soft-min of the covering
constraints, as stated below.

$\displaystyle
f_{p}(x)=\frac{1}{\eta}\cdot\log\left(\sum_{i=1}^{m_{p}}\exp(\eta
P_{i}x)\right)\text{ and
}f_{c}(x)=-\frac{1}{\eta}\cdot\log\left(\sum_{j=1}^{m_{c}}\exp(-\eta
C_{j}x)\right),$ $\displaystyle\text{ where
}\eta=\frac{\log(m_{p}+m_{c}+U/L)}{\epsilon}.$ (3.2)

It can be shown that the function $f_{p}(x)$ (resp. $f_{c}(x)$) closely
approximates the maximum (resp. minimum) value among the left hand sides of
the packing (resp. covering) constraints. Specifically, we have:

$\displaystyle\max_{i\in[m_{p}]}P_{i}x\leq
f_{p}(x)\leq\max_{i\in[m_{p}]}P_{i}x+\epsilon\text{ and
}\min_{j\in[m_{c}]}C_{j}x-\epsilon\leq
f_{c}(x)\leq\min_{j\in[m_{c}]}C_{j}x,\text{ for all }x\in\mathbb{R}_{\geq
0}^{n}.$ (3.3)

The algorithm attempts to find an $x\in\mathbb{R}_{\geq 0}^{n}$ where
$f_{p}(x)\leq 1$ and $f_{c}(x)\geq 1$. By (3.3), such an $x$ is indeed an
$\epsilon$-approximate solution to the input positive LP. Note that both the
functions $f_{p}(x)$ and $f_{c}(x)$ are continuous and differentiable, and
hence their gradients exist at all points.

####  3.1.1 The main idea

Say that a direction $z\in\mathbb{R}_{\geq 0}^{n}$ is cheap with respect to a
point $x\in\mathbb{R}_{\geq 0}^{n}$ iff $\langle\nabla
f_{p}(x),z\rangle\leq\langle\nabla f_{c}(x),z\rangle$. In other words,
starting from the point $x$, if we take an infinitesimally small step towards
a cheap direction w.r.t. $x$, then the increase in $f_{p}(x)$ is at most the
increase in $f_{c}(x)$. The high level idea behind the algorithm can be
summarised as follows: It starts at an $x=\vec{0}\in\mathbb{R}_{\geq 0}^{n}$,
where we have $f_{p}(x)=f_{c}(x)=0$. It then continuously keeps moving this
point $x$ in a cheap direction. This leads to the following invariant:
$f_{p}(x)\leq f_{c}(x)$. The algorithm stops once it reaches a point $x$ where
$f_{c}(x)=1$. Such an $x$ satisfies $f_{p}(x)\leq 1$ and $f_{c}(x)\geq 1$, and
hence is an $\epsilon$-approximate solution to the input positive LP,
according to (3.3). On the other hand, if at some point in time during this
continuous process, we reach a point $x$ that does not admit any cheap
direction, then it can be shown that the input LP is infeasible.

In order to actually implement the scheme described above, we first need to
discretise the process which keeps moving the point $x$. This discretised
process will consist of a sequence of steps. As before, initially we have
$x=\vec{0}$. At the start of each step, we identify an (approximately) cheap
direction $z\in\mathbb{R}_{\geq 0}^{n}$ w.r.t. the current $x$, which
satisfies $\langle\nabla
f_{p}(x),z\rangle\leq(1+\Theta(\epsilon))\cdot\langle\nabla
f_{c}(x),z\rangle$, and then we take a small discrete jump along that
direction by setting $x\leftarrow x+\delta z$ for some sufficiently small
$\delta>0$. It can be shown that due to each of these steps, the increase in
the value of $f_{p}(x)$ is at most $(1+\Theta(\epsilon))$ times the increase
in the value of $f_{c}(x)$, which leads to the invariant:
$f_{p}(x)\leq(1+\Theta(\epsilon))\cdot f_{c}(x)$. Furthermore, during each of
these steps, the value of $f_{c}(x)$ increases by at most $\Theta(\epsilon)$,
for sufficiently small $\delta$. The process terminates immediately after we
reach a stage where $f_{c}(x)\geq 1$. Thus, at termination we have $1\leq
f_{c}(x)\leq(1+\Theta(\epsilon))$ and
$f_{p}(x)\leq(1+\Theta(\epsilon))f_{c}(x)\leq(1+\Theta(\epsilon))$, and hence
$x$ is a $\Theta(\epsilon)$-approximate solution to the input positive LP. In
contrast, if at any step during this process, we end up with an $x$ which does
not admit any (approximately) cheap direction, then we can certify that the
input LP is infeasible.

We will work with a concrete version of the framework described above. Say
that a coordinate $k\in[n]$ is (approximately) cheap with respect to a point
$x\in\mathbb{R}_{\geq 0}^{n}$ iff $\langle\nabla
f_{p}(x),\vec{e}_{k}\rangle\leq(1+\Theta(\epsilon))\cdot\langle\nabla
f_{c}(x),\vec{e}_{k}\rangle$, where $e_{k}\in\\{0,1\\}^{n}$ is the unit vector
along coordinate $k$. We will use the following crucial observation: Any given
point $x$ admits a cheap direction iff it admits a cheap coordinate. Thus, all
we need to do is start at $x=\vec{0}$, and then move the point $x$ in a
sequence of steps, where at each step we move $x$ by a small amount along a
cheap coordinate. We now present this algorithmic template more formally in
Section 3.1.2.

####  3.1.2 The basic algorithmic template

We start by introducing some crucial notations. Given any
$x\in\mathbb{R}_{\geq 0}^{n}$, we associate a weight with each LP constraint.
To be specific, for all $i\in[m_{p}]$ and $j\in[m_{c}]$, we have
$w_{p}(x,i):=\exp\left(\eta\cdot P_{i}x\right)$ and
$w_{c}(x,j):=\exp\left(-\eta\cdot C_{j}x\right)$. Let
$w_{p}(x):=\sum_{i=1}^{m_{p}}w_{p}(x,i)$ and
$w_{c}(x):=\sum_{j=1}^{m_{c}}w_{c}(x,j)$.

######  Definition 3.2.

Consider any $k\in[n]$. The cost of coordinate $k$ at a given
$x\in\mathbb{R}^{n}_{\geq 0}$ is defined as:

$\lambda(x,k):=\frac{\sum_{i=1}^{m_{p}}w_{p}(x,i)\cdot
P(i,k)}{\sum_{j=1}^{m_{c}}w_{c}(x,j)\cdot C(j,k)}.$

The coordinate $k\in[n]$ is said to be cheap w.r.t. a given
$x\in\mathbb{R}_{\geq 0}^{n}$ iff $\lambda(x,k)\leq(1+\Theta(\epsilon))\cdot
w_{p}(x)/w_{c}(x)$.

It turns out that the notion of a cheap coordinate, as per Definition 3.2, is
identical to the one used in the last paragraph of Section 3.1.1 (see Property
3.3 and Property 3.4). The algorithm is described in Figure 8.

1. Initialise $x\leftarrow\vec{0}\in\mathbb{R}_{\geq 0}^{n}$. 2. While $\min_{j\in[m_{c}]}C_{j}x<1$: 3. If there is no cheap coordinate at $x$, Then 4. Return that the LP is infeasible. 5. Else 6. Let $k\in[n]$ be a cheap coordinate. 7. $x\leftarrow\text{{\sc Boost}}(x,k)$. // See Figure 9. 8. Return $x$.

Figure 8:  A static algorithm for solving a positive LP $(P,C)$.

1. Find the maximum $\delta$ such that $\max_{i\in[m_{p}]}P(i,k)\cdot\delta\leq\epsilon/\eta$ and $\max_{j\in[m_{c}]:C_{j}x<2}C(j,k)\cdot\delta\leq\epsilon/\eta$. 2. Return $x+\delta\vec{e}_{k}$.

Figure 9:  Boost($x,k$).

It is easy to check that this algorithm follows the framework outlined in
Section 3.1.1. To summarise, the algorithm starts at $x=\vec{0}$.
Subsequently, each iteration of the While loop in Figure 8 either declares
that the input LP is infeasible, or identifies a cheap coordinate w.r.t. the
current $x$ and calls the subroutine in Figure 9 to boost (i.e., change) $x$
by a small amount along that direction. It stops when
$\min_{j\in[m_{c}]}C_{j}x\geq 1$.

We now state two key properties of the algorithm, whose proofs are deferred to
Appendix B. Property 3.3 justifies the algorithm’s decision to declare that
the input LP is infeasible if it cannot find any cheap coordinate w.r.t. the
current $x\in\mathbb{R}_{\geq 0}^{n}$. Property 3.4 ensures that whenever the
algorithm decides to boost the current $x$ along a cheap coordinate $k\in[n]$,
the increase in $f_{p}(x)$ is at most $(1+\Theta(\epsilon))$ times the
increase in $f_{c}(x)$, which, in turn, is itself at most $\Theta(\epsilon)$.

######  Property 3.3.

Consider any $x\in\mathbb{R}_{\geq 0}^{n}$. If there is no cheap coordinate at
$x$, then the LP $(P,C)$ is infeasible.

######  Property 3.4.

Assume $\epsilon<1/10$ and let $k\in[n]$ be a cheap coordinate at
$y\in\mathbb{R}_{\geq 0}^{n}$, and let $z\leftarrow\text{{\sc Boost}}(y,k)$.
Then we have:

$f_{p}(z)-f_{p}(y)\leq(1+\Theta(\epsilon))\cdot\left(f_{c}(z)-f_{c}(y)\right)\leq\Theta(\epsilon).$

Recall that initially $x=\vec{0}$, and so $f_{p}(x)=f_{c}(x)=0$. Each
subsequent iteration of the While loop in Figure 8 boosts the current $x$
along a cheap coordinate. Hence, Property 3.4 implies the following invariant:

######  Invariant 3.5.

During the course of this algorithm, we always have
$f_{p}(x)\leq(1+\Theta(\epsilon))\cdot f_{c}(x)$. Furthermore, each call to
the subroutine Boost$(x,k)$ increases the value of $f_{c}(x)$ by at most an
additive $\Theta(\epsilon)$.

######  Corollary 3.6.

If the algorithm in Figure 8 returns an $x\in\mathbb{R}_{\geq 0}^{n}$ in step
8, then $x$ is indeed a $\Theta(\epsilon)$-approximate solution to the input
LP. Otherwise, it correctly declares that the input LP is infeasible.

###### Proof.

Case (i): The algorithm terminates in step $8$ of Figure 8. All the claims
made in the next paragraph hold because of (3.3) and Invariant 3.5.

Just before the last iteration of the While loop in Figure 8, we had
$f_{p}(x)\leq(1+\Theta(\epsilon))\cdot f_{c}(x)$ and
$f_{c}(x)\leq\min_{j\in[m_{c}]}C_{j}x<1$. Accordingly, at the end of the last
iteration of the concerned While loop, we have $\max_{i\in[m_{p}]}P_{i}x\leq
f_{p}(x)\leq(1+\Theta(\epsilon))\cdot
f_{c}(x)\leq(1+\Theta(\epsilon))\cdot(1+\Theta(\epsilon))\leq
1+\Theta(\epsilon)$, and $\min_{j\in[m_{c}]}C_{j}x\geq 1$. Hence, the $x$ that
is returned in step $8$ of Figure 8 is a $\Theta(\epsilon)$-approximate
solution to the input LP.

Case (ii): The algorithm terminates because during some iteration of the While
loop in Figure 8 it cannot find any cheap coordinate w.r.t. the current $x$.
In this case, by Property 3.3, the input LP is infeasible. ∎

###  3.2 An Overview of Our Dynamic Greedy MWU Algorithm

We describe the basic template that will be followed by our dynamic algorithm
in Section 3.2.1. For ease of exposition, in Section 3.2.2 we describe and
analyse our dynamic algorithm in a setting where all the relaxing entry
updates occur to the covering constraints, whereas the packing constraints
remain unchanged. Finally, in Section 3.2.3 we present an overview of the
complete algorithm which can handle relaxing entry updates to both the packing
and covering constraints.

####  3.2.1 The basic template for our dynamic algorithm

Initialisation: At preprocessing, we start by implementing the procedure
described in Figure 8. At this stage, if we end up with a
$\Theta(\epsilon)$-approximate solution $x$ to the positive LP, then we are
done. This is because such an $x$ will continue to remain a
$\Theta(\epsilon)$-approximate solution to the input LP even after it
undergoes any sequence of relaxing updates in future. Accordingly, henceforth
we assume that the procedure in Figure 8 ends up with an $x$ at which there is
no cheap coordinate.

Handling a relaxing update: After the update, we keep on boosting $x$ along
cheap coordinates until either (a) the set of cheap coordinates becomes empty
again, or (b) we have $\min_{j\in[m_{c}]}C_{j}\geq 1$. In the former case, we
declare that the input LP remains infeasible even after the relaxing update.
In the latter case, we declare the current $x$ as a
$\Theta(\epsilon)$-approximate solution to the input LP from this point
onward.

Clearly, as per the discussion in Section 3.1, any dynamic algorithm following
the above template solves the problem of maintaining a
$\Theta(\epsilon)$-approximate solution to a positive LP under relaxing
updates.

####  3.2.2 Handling a sequence of relaxing entry updates to the covering
constraints

We now present an overview of our dynamic algorithm, under the assumption that
every relaxing update increases the value of some entry in the matrix $C$
(whereas the matrix $P$ remains unchanged). We follow the template outlined in
Section 3.2.1. The main challenge is to define the appropriate data
structures, and to describe how to choose a cheap coordinate for boosting $x$
at any given point in time.

Before proceeding any further, note that there are two types of events which
influence the outcome of any dynamic algorithm following the template from
Section 3.2.1: (1) a relaxing update which increases the value of some entry
in the matrix $C$, and (2) a call to the subroutine $\text{{\sc Boost}}(x,k)$
which boosts the current $x$ along the coordinate $k$. We start with the key
invariant that drives the analysis of our dynamic algorithm.

######  Invariant 3.7.

During the course of our dynamic algorithm, we always have
$f_{p}(x)\leq(1+\Theta(\epsilon))\cdot f_{c}(x)$. Furthermore, every call to
the subroutine Boost$(x,k)$ increases $f_{c}(x)$ by at most an additive
$\Theta(\epsilon)$.

###### Proof.

The algorithm starts at $x=\vec{0}$, where $f_{p}(x)=f_{c}(x)=0$ and so the
invariant holds. Subsequently, the values of $f_{p}(x)$ and $f_{c}(x)$ can
change because of one of the two following types of events.

(1) A relaxing update increases the value of an entry $C(j,k)$ of the matrix
$C$, for $j\in[m_{c}]$, $k\in[n]$. This increases the value of $C_{j}x$;
whereas for all $j^{\prime}\in[m_{c}]\setminus\\{j\\}$ and $i\in[m_{p}]$, the
values of $C_{j^{\prime}}x$ and $P_{i}x$ remain unchanged. We accordingly
infer that $f_{c}(x)$ increases, whereas $f_{p}(x)$ remains unchanged. Thus,
if the invariant was true just before this event, then it continues to remain
true just after the event.

(2) The algorithm make a call to Boost$(x,k)$, for some $k\in[n]$. By Property
3.4, due to this event the increase in $f_{p}(x)$ is at most
$(1+\Theta(\epsilon))$ times the increase in $f_{c}(x)$, and this latter
quantity is at most $\Theta(\epsilon)$. Thus, if the invariant was true just
before this event, then it continues to remain true just after the event. ∎

######  Corollary 3.8.

During the course of our dynamic algorithm, we always have
$\max_{i\in[m_{p}]}P_{i}x\leq 1+\Theta(\epsilon)$.

###### Proof.

Follows from (3.3), Invariant 3.7, and the fact that we return $x$ the moment
$\min_{j\in[m_{c}]}C_{j}x$ is $\geq 1$. ∎

Next, we derive a few important observations which show that the weights
$w_{p}(x,i),w_{c}(x,j)$ of the constraints and the costs $\lambda(x,k)$ of the
coordinates change (almost) monotonically over time.

######  Observation 3.9.

Consider an event which consists of either a relaxing update to the matrix $C$
or a call to the subroutine Boost$(x,k)$. Such an event can only increase the
weight $w_{p}(x,i)$ of a packing constraint $i\in[m_{p}]$, and it can only
decrease the weight $w_{c}(x,j)$ of a covering constraint $j\in[m_{c}]$.

###### Proof.

Consider a relaxing update which increases the value of some entry $C(j,k)$ of
the matrix $C$. This increases the value of $C_{j}x$; whereas for all
$j^{\prime}\in[m_{c}]\setminus\\{j\\}$ and $i\in[m_{p}]$, the values of
$C_{j^{\prime}}x$ and $P_{i}x$ remain unchanged. Accordingly, this event
decreases the weight $w_{c}(x,j)$; whereas for all
$j^{\prime}\in[m_{c}]\setminus\\{j\\}$ and $i\in[m_{p}]$, the weights
$w_{c}(x,j^{\prime})$ and $w_{p}(x,i)$ remain unchanged due to this event.

Next, consider a call to Boost$(x,k)$. For all $i\in[m_{p}]$ with $P(i,k)>0$
this increases the value of $P_{i}x$, whereas for all $i\in[m_{p}]$ with
$P(i,k)=0$ the value of $P_{i}x$ remains unchanged. Similarly, for all
$j\in[m_{c}]$ with $C(j,k)>0$ this increases the value of $C_{j}x$, whereas
for all $j\in[m_{c}]$ with $C(j,k)=0$ the value of $C_{j}x$ remains unchanged.
In effect, this means that for all $i\in[m_{p}]$ the weight $w_{p}(x,i)$ can
only increase due to this event, whereas for all $j\in[m_{p}]$ the weight
$w_{c}(x,j)$ can only decrease due to this event. ∎

######  Observation 3.10.

Consider an event which consists of a call to the subroutine Boost$(x,k)$ for
some $k\in[n]$. Because of this event, the cost $\lambda(x,k^{\prime})$ of any
coordinate $k^{\prime}\in[n]$ can only increase.

###### Proof.

Follows from Observation 3.9 and Definition 3.2. ∎

######  Observation 3.11.

Consider a relaxing update to the entry $C(j,k)$ of the matrix $C$, where
$j\in[m_{c}]$, $k\in[n]$. Because of this event, the cost
$\lambda(x,k^{\prime})$ of a coordinate $k^{\prime}\in[n]\setminus\\{k\\}$ can
only increase, whereas the cost of the coordinate $k$ can change in either
direction (i.e., it can increase or decrease).

###### Proof.

Because of this relaxing update, the value of $C(j,k)$ increases, whereas the
values of all other entries in the matrices $C$ and $P$ remain unchanged. The
proof follows from Observation 3.9 and Definition 3.2. ∎

Key data structures: We will explicitly maintain the following quantities: (1)
The point $x\in\mathbb{R}_{\geq 0}^{n}$. (2) The weights
$w_{p}(x,i),w_{c}(x,j)$ for all $i\in[m_{p}],j\in[m_{c}]$. (3) The total
weights $w_{p}(x)$ and $w_{c}(x)$. (4) The values of $P_{i}x$ and $C_{j}x$,
for all $i\in[m_{p}]$ and $j\in[m_{c}]$.

We are now ready to describe the exact implementation of our dynamic algorithm
in more details.

Phases: Observation 3.9 implies that the ratio $\gamma(x):=w_{p}(x)/w_{c}(x)$
increases monotonically over time during the course of our algorithm. Armed
with this observation, we split the working of our algorithm into phases. In
the beginning, we have $x=\vec{0}$ and hence
$\gamma(x)=w_{p}(x)/w_{c}(x)=1/1=1$. We initiate a new phase whenever the
value of $\gamma(x)$ increases by a multiplicative factor of
$(1+\Theta(\epsilon))$. Thus, a given phase can span a sequence of calls to
the Boost$(x,k)$ subroutine at preprocessing, or it can also span a sequence
of calls to the Boost$(x,k)$ subroutine interspersed with a sequence of
relaxing updates to the matrix $C$.

Implementing a given phase: Let $\gamma^{0}(x)$ be the value of
$\gamma(x):=w_{p}(x)/w_{c}(x)$ at the start of the phase. During the phase,
$\gamma(x)$ does not change by more than an $(1+\Theta(\epsilon))$ factor.
Accordingly, at any point in time within the phase, we classify a coordinate
$k\in[n]$ as being cheap iff
$\lambda(x,k)\leq(1+\Theta(\epsilon))\cdot\gamma^{0}(x)$.

We maintain a set $E\subseteq[n]$ that always contains all the coordinates
that are currently cheap. At the start of the phase, we initialise
$E\leftarrow[n]$, and then call the subroutine Boost-All$(x,E)$ which is
described in Figure 10. Note that at the end of any iteration of the inner
While loop (steps 4 – 9 in Figure 10), the concerned coordinate $k$ is no
longer cheap. Furthermore, the monotonicity of the costs (as captured by
Observation 3.10) imply that a coordinate $k$, once removed from the set $E$,
does not become cheap again within the same phase due to some future iteration
of the outer While loop in Figure 10.

Handling a relaxing update within the phase: Consider a relaxing update to an
entry $C(j,k)$ of the matrix $C$. Just before this update, we had
$E=\emptyset$. If the value of $\gamma(x)$ becomes more than
$(1+\Theta(\epsilon))\gamma^{0}(x)$ because of this update, then we terminate
the current phase and initiate a new one. Otherwise, by Observation 3.11, the
only coordinate that can become cheap because of this update is $k$.
Accordingly, we set $E\leftarrow\\{k\\}$, and call the subroutine Boost-
All$(x,E)$. Observation 3.10 again implies that as we keep boosting $x$ along
the coordinate $k$, it does not lead to any other coordinate
$k^{\prime}\in[n]\setminus\\{k\\}$ becoming cheap.

1. While $E\neq\emptyset$: 2. Consider any $k\in E$. 3. $E\leftarrow E\setminus\\{k\\}$. 4. While $\lambda(x,k)\leq(1+\Theta(\epsilon))\cdot\gamma^{0}(x)$ 5. $x\leftarrow\text{{\sc Boost}}(x,k)$. // See Figure 9. 6. If $\min_{j\in[m_{c}]}C_{j}x\geq 1$, Then 7. Return $x$. 8. If $\gamma(x)>(1+\Theta(\epsilon))\cdot\gamma^{0}(x)$, Then 9. Terminate the current phase.

Figure 10:  Boost-All$(x,E)$.

The next two lemmas capture a couple of crucial properties of this dynamic
algorithm.

######  Lemma 3.12.

Fix any coordinate $k\in[n]$. The dynamic algorithm described above calls the
subroutine Boost$(x,k)$ at most
$O\left(\frac{\log^{2}(m_{c}+m_{p}+U/L)}{\epsilon^{2}}\right)$ many times.

###### Proof.

Fix a coordinate $k\in[n]$ for the rest of the proof.

Consider any call to the Boost$(x,k)$ subroutine during the course of our
dynamic algorithm, which increases coordinate $k$ of the vector
$x\in\mathbb{R}_{\geq 0}^{n}$ by some amount $\delta>0$. From Figure 9,
observe that just before this specific call to the subroutine, either there
exists a packing constraint $i\in[m_{p}]$ with
$P(i,k)\cdot\delta=\epsilon/\eta$, or there exists a not-too-large covering
constraint $j\in[m_{c}]$151515We say that a covering constraint $j\in[m_{c}]$
is not-too-large iff $C_{j}x<2$. with $C(j,k)\cdot\delta=\epsilon/\eta$. In
the former (resp. latter) case, we refer to the index $i$ (resp. $j$) as the
pivot and the current value of $P(i,k)$ (resp. $C(j,k)$) as the pivot-value
corresponding to this specific call to the subroutine Boost$(x,k)$.161616Note
that the values of the entries in the constraint matrix change over time due
to the sequence of updates. The pivot-value of a call to Boost$(x,k)$ refers
to the value of the concerned entry in the constraint matrix just before the
specific call to Boost$(x,k)$.

Without loss of generality, assume that $U=2^{\tau}\cdot L$ where
$\tau=\log(U/L)$ is an integer, and that the value of any nonzero entry in the
constraint matrix lies in the interval $(L,U]$ at all times. Partition the
interval $(L,U]$ into $\tau$ segments
$\mathcal{I}_{0},\ldots,\mathcal{I}_{\tau-1}$, where
$\mathcal{I}_{\ell}=\left(L\cdot 2^{\ell},L\cdot 2^{\ell+1}\right]$ for all
$\ell\in\\{0,\ldots,\tau-1\\}$.

######  Claim 3.1.

Consider any $\ell\in\\{0,\ldots,\tau-1\\}$. Throughout the duration of our
dynamic algorithm, at most $4\eta/\epsilon$ calls with pivot-values in
$\mathcal{I}_{\ell}$ and pivots in $[m_{c}]$ are made to the Boost$(x,k)$
subroutine (see (3.2)).

###### Proof.

Let $x_{k}\in\mathbb{R}_{\geq 0}$ denote the $k^{th}$ coordinate of the vector
$x\in\mathbb{R}_{\geq 0}^{n}$. For ease of exposition, we say that a call to
Boost$(x,k)$ is covering-critical iff its pivot is in $[m_{c}]$ and its pivot-
value is in $\mathcal{I}_{\ell}$. We wish to upper bound the total number of
covering-critical calls made during the course of our dynamic algorithm.

Consider any specific covering-critical call to Boost$(x,k)$ with pivot
$j\in[m_{c}]$ and pivot-value $\alpha\in\mathcal{I}_{\ell}=\left(L\cdot
2^{\ell-1},L\cdot 2^{\ell}\right]$. From Figure 9, it follows that this call
increases $x_{k}$ by $\delta=\epsilon/(\eta\alpha)\geq\epsilon/(\eta
L2^{\ell})$.

Suppose that $T$ covering-critical calls have been made to the Boost$(x,k)$
subroutine, where $T>4\eta/\epsilon$. Let us denote these calls in increasing
order of time by: $\Gamma_{1},\Gamma_{2},\ldots,\Gamma_{T}$. Thus, for all
$t\in[T]$, we let $\Gamma_{t}$ denote the $t^{th}$ covering-critical call made
during the course of our dynamic algorithm. From the discussion in the
preceding paragraph, each of these critical calls $\Gamma_{t}$ increases
$x_{k}$ by at least $\epsilon/(\eta L2^{\ell})$.

Initially $x_{k}=0$, and it increases monotonically over time. Hence, just
before the last critical call $\Gamma_{T}$ we have
$x_{k}\geq(T-1)\cdot\epsilon/(\eta
L2^{\ell})\geq(4\eta/\epsilon)\cdot\epsilon/(\eta L2^{\ell})=1/(L2^{\ell-2})$.
Let $j_{T}\in[m_{c}]$ be the pivot of the call $\Gamma_{T}$. Since the pivot-
value of $\Gamma_{T}$ lies in $\mathcal{I}_{\ell}$, it follows that
$C(j_{T},k)>L\cdot 2^{\ell-1}$ just before the call $\Gamma_{T}$. Thus, just
before the call $\Gamma_{T}$, we have $C_{j_{T}}\cdot x\geq C(j_{T},k)\cdot
x_{k}>L2^{\ell-1}\cdot 1/(L2^{\ell-2})=2$. But if $C_{j_{T}}\cdot x>2$ just
before the call $\Gamma_{T}$, then $j_{T}$ cannot be the pivot of $\Gamma_{T}$
(see Figure 9). This leads to a contradiction. Hence, we must have $T\leq
4\eta/\epsilon$, and this concludes the proof of the claim. ∎

######  Claim 3.2.

Consider any $\ell\in\\{0,\ldots,\tau-1\\}$. Throughout the duration of our
dynamic algorithm, at most $4\eta/\epsilon$ calls with pivot-values in
$\mathcal{I}_{\ell}$ and pivots $i\in[m_{p}]$ are made to the Boost$(x,k)$
subroutine (see (3.2)).

###### Proof.

(Sketch) As in the proof of Claim 3.1, let $x_{k}\in\mathbb{R}_{\geq 0}$
denote the $k^{th}$ coordinate of the vector $x\in\mathbb{R}_{\geq 0}^{n}$.
Say that a call to Boost$(x,k)$ is packing-critical iff its pivot is in
$[m_{p}]$ and its pivot-value is in $\mathcal{I}_{\ell}$.

Suppose that $T$ covering-critical calls have been made to the Boost$(x,k)$
subroutine, where $T>4\eta/\epsilon$. Let us denote these calls in increasing
order of time by: $\Gamma_{1},\Gamma_{2},\ldots,\Gamma_{T}$. Thus, for all
$t\in[T]$, we let $\Gamma_{t}$ denote the $t^{th}$ packing-critical call made
during the course of our dynamic algorithm. Let $i_{T}\in[m_{p}]$ be the pivot
of the last packing-critical call $\Gamma_{T}$. Following the same argument as
in the proof of Claim 3.1, we conclude that $P_{i_{T}}\cdot x>2$ just before
the call $\Gamma_{T}$. But if $P_{i_{T}}\cdot x>2$, then
$f_{p}(x)\geq\max_{i\in[m_{p}]}P_{i}x>2$ according to (3.3). Now, applying
Invariant 3.7, we conclude that just before the call $\Gamma_{T}$ we have:
$\min_{j\in[m_{c}]}C_{j}x\geq f_{c}(x)\geq(1+\epsilon)^{-1}\cdot
f_{p}(x)>(1+\epsilon)^{-1}\cdot 2>1$. This leads to a contradiction, since if
$\min_{j\in[m_{c}]}C_{j}x>1$, then our dynamic algorithm would immediately
declare that it has found a $\Theta(\epsilon)$-approximate solution to the
input LP from this point onward, without making any further calls to the
Boost$(x,k)$ subroutine (in particular, without making the call $\Gamma_{T}$).
Thus, it must be the case that $T\leq 4\eta/\epsilon$, and this concludes the
proof of the claim. ∎

Any call to the Boost$(x,k)$ subroutine has its pivot in $[m_{p}]\cup[m_{c}]$
and pivot-value in $\mathcal{I}_{\ell}$, for some
$\ell\in\\{0,\ldots,\tau-1\\}$.171717This holds because the pivot-values lie
in the range $(L,U]$, and this range has been partitioned into subintervals:
$\mathcal{I}_{0},\ldots,\mathcal{I}_{\tau-1}$.  Thus, Claim 3.1 and Claim 3.2
imply that the total number of calls made to the Boost$(x,k)$ subroutine is at
most
$2\cdot\tau\cdot(4\eta/\epsilon)=O\left(\frac{\log^{2}(m_{c}+m_{p}+U/L)}{\epsilon^{2}}\right)$.
∎

######  Lemma 3.13.

The dynamic algorithm described above has at most
$O\left(\frac{\log(m_{c}+m_{p}+U/L)}{\epsilon^{2}}\right)$ many phases.

###### Proof.

By Observation 3.9, the ratio $\gamma(x):=w_{p}(x)/w_{c}(x)$ increases
monotonically over time. Initially, we have $x=\vec{0}$, and hence
$\gamma(x)=w_{p}(x)/w_{c}(x)=1$. Let $\kappa$ be the time-instant at which the
last ever call to Boost$(x,k)$ is made by our dynamic algorithm. We will upper
bound $\gamma(x)$ just before the time-instant $\kappa$.

Just before the time-instant $\kappa$, by Corollary 3.8 we have
$\max_{i\in[m_{p}]}P_{i}x\leq 1+\Theta(\epsilon)$ and hence
$w_{p}(x,i)\leq\exp(\eta(1+\Theta(\epsilon)))$ for all $i\in[m_{p}]$, which
implies that $w_{p}(x)=\sum_{i=1}^{m_{p}}w_{p}(x,i)\leq
m_{p}\cdot\exp(\eta(1+\Theta(\epsilon)))$.

Just before the time-instant $\kappa$, we also have
$\min_{j\in[m_{c}]}C_{j}x<1$. Hence, at that moment there exists some
$j^{\prime}\in[m_{c}]$ with $C_{j^{\prime}}x<1$ and $w_{c}(x,j^{\prime})\geq
1/\exp(\eta)$. This means that $w_{c}(x)\geq w_{c}(x,j^{\prime})\geq
1/\exp(\eta)$.

To summarise, we infer that $\gamma(x)=w_{p}(x)/w_{c}(x)\leq
m_{p}\cdot\exp(\eta(1+\Theta(\epsilon)))\cdot\exp(\eta)=O(m_{p}\cdot\exp(3\cdot\eta))$
just before the time-instant $\kappa$. Thus, the value of $\gamma(x)$
increases from $1$ at the start of the algorithm to at most
$\Lambda=O(\exp(3\cdot\eta)\cdot m_{p})$ just before the last call to the
Boost$(x,k)$ subroutine.

Note that $\gamma(x)$ increases monotonically over time in the range
$[1,\Lambda]$, and we create a new phase whenever $\gamma(x)$ increases by a
$(1+\Theta(\epsilon))$ factor. Thus, from (3.2), we conclude that the total
number of phases is at most
$\log_{(1+\Theta(\epsilon))}\Lambda=O\left(\frac{\log(m_{p}+m_{c}+U/L)}{\epsilon^{2}}\right)$.
∎

Analysing the total update time: We first focus on bounding the total time
spent on all the calls to the Boost$(x,k)$ subroutine during the course of our
algorithm. By Lemma 3.12, the point $x$ gets boosted along a given coordinate
$k\in[n]$ at most
$\Gamma=O\left(\frac{\log^{2}(m_{c}+m_{p}+U/L)}{\epsilon^{2}}\right)$ times.