Whenever we boost $x$ along some coordinate $k$, we need to spend $O(nz(k))$
time to update all the relevant weights $\\{w_{p}(x,i)\\}$,
$\\{w_{c}(x,j)\\}$, $w_{p}(x)$, $w_{c}(x)$ and the values
$\\{C_{j}x\\},\\{P_{i}x\\}$; where $nz(k)$ is the total number of nonzero
entries in the $k^{th}$ column of the matrices $P,C$ at the current moment.
Hence, the total time spent in all the calls to the Boost$(x,k)$ subroutine is
at most $\sum_{k=1}^{n}\Gamma\cdot O(nz(k))=\Gamma\cdot
O(N)=O\left(N\cdot\frac{\log^{2}(m_{c}+m_{p}+U/L)}{\epsilon^{2}}\right)$.

Next, note that whenever we create a new phase, we set $E\leftarrow[n]$ and
call the subroutine Boost-All$(x,E)$ as in Figure 10. Also, whenever there is
a relaxing update to an entry $C(j,k)$ in the covering matrix, we set
$E\leftarrow\\{k\\}$ and then make a call to Boost-All$(x,E)$. Thus, it might
very well be the case that a coordinate $k\in[n]$ moves in and out of the set
$E$ on multiple occasions, without being boosted at all. The time spent on
these apparently futile operations, which modify the set $E$ without leading
to any call to Boost$(x,k)$, is captured by steps 1–3 of Figure 10. Lemma 3.13
implies that the total time spent in this manner, throughout a sequence of $t$
relaxing updates and across all the coordinates, is at most:

$\displaystyle(\text{number of phases})\cdot O(\text{number of
coordinates})+O(t)$ $\displaystyle=$ $\displaystyle
O\left(n\cdot\frac{\log(m_{c}+m_{p}+U/L)}{\epsilon^{2}}+t\right)$
$\displaystyle=$ $\displaystyle
O\left(N\cdot\frac{\log(m_{c}+m_{p}+U/L)}{\epsilon^{2}}+t\right).$

Finally, note that the preprocessing time is at most
$O\left(N\cdot\frac{\log(m_{c}+m_{p})}{\epsilon^{2}}\right)$, since the static
algorithm from Section 3.1 can be implemented in
$O\left(N\cdot\frac{\log(m_{c}+m_{p})}{\epsilon^{2}}\right)$ time [You14].
This leads us to Theorem 3.1 for relaxing entry updates to covering
constraints.

####  3.2.3 The full algorithm: Handling relaxing entry updates to both
packing and covering constraints

We start by identifying the main difficulty in extending the dynamic algorithm
from Section 3.2.2 to the setting where relaxing updates occur to both packing
and covering constraints of the input positive LP. Consider a relaxing update
to the entry $P(i,k)$, for some $i\in[m_{p}],k\in[n]$. Due to this relaxing
update, the value of $P(i,k)$ gets reduced, and accordingly the weight
$w_{p}(x,i)$ also decreases. This contradicts the monotonicity of the weights
as captured in Observation 3.9. Thus, $w_{p}(x)$ no longer increases
monotonically with time, which in turn invalidates the proof of Lemma 3.13. We
circumvent this difficulty by working with an extended positive LP
$(P^{*},C^{*})$, which is derived from the input LP $(P,C)$ in the following
manner.

The extended LP: Throughout the sequence of updates to the input LP, we ensure
that we always have:

  * •

$P^{*}\in\mathbb{R}_{\geq 0}^{m_{p}\times(n+1)}$, where $P^{*}(i,k)=P(i,k)$
and $P^{*}(i,n+1)\geq 0$ for all $i\in[m_{p}],k\in[n]$.

  * •

$C^{*}\in\mathbb{R}_{\geq 0}^{m_{c}\times(n+1)}$, where $C^{*}(j,k)=C(j,k)$
and $C^{*}(j,n+1)=0$ for all $j\in[m_{c}],k\in[n]$.

It is easy to check that the input LP $(P,C)$ is feasible iff the extended LP
$(P^{*},C^{*})$ is feasible. Furthermore, if
$x^{*}=(x^{*}_{1},\ldots,x^{*}_{n+1})\in\mathbb{R}_{\geq 0}^{n+1}$ is a
$\Theta(\epsilon)$-approximate solution to the extended LP $(P^{*},C^{*})$,
then $x=(x^{*}_{1},\ldots,x^{*}_{n})\in\mathbb{R}_{\geq 0}^{n}$ is a
$\Theta(\epsilon)$-approximate solution to the input LP $(P,C)$. Accordingly,
our new dynamic algorithm will attempt to approximately solve the extended LP
$(P^{*},C^{*})$. Note that we are free to set the values $P^{*}(i,n+1)$ of the
matrix $P^{*}$ in any way we chose (provided they remain nonnegative). We will
use this to our advantage while dealing with relaxing updates to the packing
constraints in the input LP. It is important to emphasise that except the
entries $P^{*}(i,n+1)$, at any point in time the values of all other entries
in the matrices $P^{*}$ and $C^{*}$ are determined by the current status of
the input LP $(P,C)$.

Initialisation: At preprocessing, we set $P^{*}(i,n+1)\leftarrow 0$ for all
$i\in[m_{p}]$. We start with an
$x^{*}=(x^{*}_{1},\ldots,x^{*}_{n+1})\in\mathbb{R}_{\geq 0}^{n+1}$ where
$x^{*}_{1}=\cdots=x^{*}_{n}=0$ and $x^{*}_{n+1}=1$. At this point in time, we
have $f_{p}(x^{*})=f_{c}(x^{*})=0$. From this point onward, we will keep
modifying $x^{*}$ until it becomes a $\Theta(\epsilon)$-approximate solution
to the extended LP $(P^{*},C^{*})$, by following the same template as outlined
in Section 3.2.1 and Section 3.2.2. In addition, now after every relaxing
update to an entry in the packing matrix (say) $P(i,k)$, we will change the
value of $P^{*}(i,n+1)$ in such a way that works to our advantage. This is
explained in more details below. For clarity of exposition, henceforth we
assume that after an update to an entry $P(i,k)$ (resp. $C(j,k)$) of the
matrix $P$ (resp. $C$), the corresponding entry $P^{*}(i,k)$ (resp.
$C^{*}(j,k)$) implicitly gets updated so as to ensure the equality
$P^{*}(i,k)=P(i,k)$ (resp. $C^{*}(j,k)=C(j,k)$).

Pseudo-updates to the extended LP: Consider any relaxing update to an entry
$P(i,k)$ of the matrix $P$, where $i\in[m_{p}],k\in[n]$. Immediately after
this relaxing update, we increase the value of $P^{*}(i,n+1)$ to such an
extent that the value of $P^{*}_{i}x^{*}$ (and hence the weight
$w_{p}(x^{*})$) remains unchanged. We refer to this step as a pseudo-update to
the extended LP. The only purpose behind the pseudo-update is to ensure that
the monotonicity of the weights as captured by Observation 3.9 continues to
hold.

In summary, the overall algorithm follows the same template as in Section
3.2.1 and Section 3.2.2, with the following caveat: Immediately after every
relaxing update to a packing constraint in the input LP, we perform the
corresponding pseudo-update to the extended LP so as to ensure the validity of
Observation 3.9. It is easy to check that all the observations, lemmas and
inferences derived in Section 3.2.2 continue to hold here. This leads us to
the dynamic algorithm promised in Theorem 3.1, for relaxing entry updates.

###  3.3 Handling Restricting (resp. Relaxing) Updates to a Packing (resp.
Covering) LP

Consider the setting where we wish to maintain a solution to Problem 2.1 when
the matrix $C$ is undergoing relaxing entry updates (or equivalently, the
matric $C^{\top}$ is undergoing restricting entry updates). Thus, each update
increases the value of some entry of $C$. The idea is simple. We run the
dynamic algorithm from Section 3.2 on the positive LP defined by (3.4) and
(3.5), which is undergoing relaxing entry updates.

$\displaystyle\mathbb{1}^{\top}x$ $\displaystyle\leq$ $\displaystyle 1$ (3.4)
$\displaystyle Cx$ $\displaystyle\geq$ $\displaystyle\mathbb{1}$ (3.5)

Suppose that this algorithm has just finished processing an update. Consider
two possible cases.

Case I: The algorithm returns a solution $x\in\mathbb{R}_{\geq 0}^{n}$ which
satisfies $\mathbb{1}^{\top}x\leq 1+\Theta(\epsilon)$ and
$Cx\geq(1-\Theta(\epsilon))\cdot\mathbb{1}$. In this case, we simply return
the vector $x$ and terminate our algorithm. The vector $x$ will continue to
remain an $\epsilon$-approximate solution to the input LP after any future
update.

Case II: The algorithm declares that the positive LP is infeasible as there is
no cheap co-ordinate. From Section 3.1.2, recall that $w_{c}(x,j)$ denotes the
weight of a covering constraint $j\in[m]$, and that
$w_{c}(x)=\sum_{j\in[m]}w_{c}(x,j)$ denotes the total weight of all the
covering constraints. Define the vector $\hat{y}\in\mathbb{R}_{\geq 0}^{m}$,
where $\hat{y}_{j}=w_{c}(x,j)/w_{c}(x)$ for all $j\in[m]$. We now claim that
$\hat{y}$ is a feasible solution to the dual packing LP.

######  Claim 3.3.

We have $\mathbb{1}^{\top}\hat{y}=1$ and $C^{\top}\hat{y}\leq\mathbb{1}$.

###### Proof.

Since $\\{\hat{y}_{j}\\}$ denotes the normalized weights of the covering
constraints, we have $\mathbb{1}^{\top}\hat{y}=1$. Next, fix any $k\in[n]$.
Since we are in Case II, the coordinate $k$ is not cheap. So, from Definition
3.2, we infer that:

$\frac{1}{\sum_{j\in[m]}\hat{y}_{j}\cdot C(j,k)}\geq 1+\Theta(\epsilon),\text{
or equivalently,
}\left(C^{\top}\hat{y}\right)_{k}=\sum_{j\in[m]}\hat{y}_{j}\cdot C(j,k)\leq
1-\Theta(\epsilon)\leq 1.$

Accordingly, we get $C^{\top}\hat{y}\leq\mathbb{1}$. ∎

Our algorithm maintains an estimate
$w^{*}_{c}(x)\in\left[w_{c}(x),(1+\epsilon)w_{c}(x)\right]$. If after
processing an update, we end up in Case II, then we return a
$y\in\mathbb{R}_{\geq 0}^{m}$, where $y_{j}:=w_{c}(x,j)/w^{*}_{c}(x)$ for all
$j\in[m]$. As $\hat{y}_{j}\leq y_{j}\leq(1+\Theta(\epsilon))\cdot\hat{y}_{j}$
for all $j\in[m]$, Claim 3.3 implies that $\mathbb{1}^{\top}y\geq 1$ and
$C^{\top}y\leq(1+\Theta(\epsilon))\cdot\mathbb{1}$.

It is easy to maintain the vector $y$ without any significant overhead in the
total update time, because of three reasons: (1) the algorithm from Section
3.2 explicitly maintains the weight $w_{c}(x,j)$ for each $j\in[m]$, (2) we do
not need to change the estimate $w^{*}_{c}(x)$ as long as we remain in the
same phase, and (3) by Lemma 3.13 we have at most
$O\left(\frac{\log(m+U/L)}{\epsilon^{2}}\right)$ many phases. Note that
whenever we start a new phase we have to spend $O(m)$ time to update the
vector $y$. Theorem 3.14 now follows from Theorem 3.1.

######  Theorem 3.14.

We can deterministically maintain a solution to Problem 2.1 when the matrix
$C$ undergoes $t$ relaxing entry updates in
$O\left(t+N\cdot\frac{\log^{2}(m+U/L)}{\epsilon^{2}}+m\cdot\frac{\log(m+U/L)}{\epsilon^{2}}\right)=O\left(t+N\cdot\frac{\log^{2}(m+U/L)}{\epsilon^{2}}\right)$
total time, where $N$ denotes the maximum number of non-zero entries in $C$
throughout these updates.

Finally, we consider the problem of maintaining an $\epsilon$-approximate
optimal solution to a generic covering (resp. packing) LP under relaxing
(resp. restricting) updates. It is easy to verify that if we start with
Theorem 3.14 and apply the same reduction outlined in Section 2.5.2, then we
obtain the following result.

######  Theorem 3.15.

Consider any sequence of $t$ relaxing updates to LP (2.13), where each update
either increases an entry of $C$, or decreases an entry of $a,b$. Throughout
these updates, let $N$ denote the maximum number of non-zero entries in $C$,
and let $L$ (resp. $U$) be 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(t\cdot\frac{\log(nU/L)}{\epsilon}+N\cdot\frac{\log^{2}(m+U/L)}{\epsilon^{3}}\cdot\log(nU/L)\right)$
total time. The same guarantee also holds for maintaining an
$\epsilon$-approximate solution to LP (2.14) under restricting updates.

##  4 Conditional Lower Bounds

In previous sections, we presented partially dynamic algorithms for packing-
covering LP-s with polylogarithmic amortized update times. This leads to a
couple of natural questions: (1) Can we solve the same problem in
polylogarithmic worst case update time? (2) Can we design a fully dynamic
algorithm for packing-covering LPs in polylogarithmic amortized update time?
We will now provide conditional lower bounds that rule out the possibility of
having these stronger guarantees.

Our lower bounds hold under Strong Exponential Time Hypothesis (SETH), and the
starting points of our reductions are Problem 4.1 and Theorem 4.2 described
below [ARW17].

######  Problem 4.1.

As input, we get four parameters $N,k,m,\beta^{*}$ such that
$\Theta\left(N^{o(1)}\right)=\beta^{*}\leq k\leq
m=\Theta\left(N^{o(1)}\right)$, and two collections of $N$ vectors
$A=\left\\{a^{(1)},\ldots,a^{(N)}\right\\}$ and
$B=\left\\{b^{(1)},\ldots,b^{(N)}\right\\}$ such that $a,b\in\\{0,1\\}^{m}$
for all $a\in A,b\in B$. Furthermore, each vector $b\in B$ has exactly $k$
non-zero entries. We want to design an algorithm that can distinguish between
the following two cases.

  * •

(1) There exists some $a\in A$ and $b\in B$ such that $a\geq b$.

  * •

(2) For all $a\in A$ and $b\in B$, we have $a\cdot b\leq
k^{*}:=\frac{k}{\beta^{*}}$.

######  Theorem 4.2.

[ARW17] Under SETH, any algorithm for Problem 4.1 runs in
$\Omega(N^{2-\epsilon})$ time for all $\epsilon>0$.

Now, we are ready to prove Theorem 1.2, and we state a more detailed version
of it below.

######  Theorem 4.3.

Assume SETH holds. Let $N$ and Opt respectively denote the number of non-zero
entries in the input LP and its optimal objective value. Then there exists
some $\beta=\Theta\left(N^{o(1)}\right)$ such that:

  * •

(i) Any algorithm which maintains an estimate $\frac{\text{{\sc
Opt}}}{\beta}\leq\nu\leq\text{{\sc Opt}}$ for a packing or covering LP under
fully dynamic entry updates must have an amortized update time of
$\Omega(N^{1-o(1)})$.

  * •

(ii) Any algorithm which maintains an estimate $\frac{\text{{\sc
Opt}}}{\beta}\leq\nu\leq\text{{\sc Opt}}$ for a packing or covering LP under
partially dynamic entry updates must have a worst-case update time of
$\Omega(N^{1-o(1)})$.

Furthermore, the same lower bounds hold even under translation updates.

###  4.1 Proof of Theorem 4.3 \- part (i)

We prove the theorem for packing LPs. The proof for covering LPs immediately
follows via LP duality.

Recall the parameters $N,k,m,\beta^{*}$ from the statement of Problem 4.1. Set
$\beta:=\beta^{*}/3$. Suppose that there is a dynamic algorithm $\mathcal{A}$
that maintains an estimate $\frac{\text{{\sc
Opt}}}{\beta}\leq\nu\leq\text{{\sc Opt}}$ for a packing LP undergoing fully
dynamic entry updates in $\Theta(T)$ amortized update time. Using
$\mathcal{A}$ as a subroutine, we design a static algorithm $\mathcal{A}^{*}$
for Problem 4.1, as described below.

Upon receiving its input, the algorithm $\mathcal{A}^{*}$ defines the
following packing LP, where initially we have $\lambda_{j}=1$ for all
$j\in[m]$. The algorithm $\mathcal{A}^{*}$ now feeds this packing LP as an
input to $\mathcal{A}$ at pre-processing.

$\displaystyle\text{Maximize }\sum_{j=1}^{m}x_{j}$ (4.1)
$\displaystyle\text{s.t. }\ \ a\cdot x$ $\displaystyle\leq$ $\displaystyle
k^{*}\qquad\text{ for all }a\in A.$ (4.2) $\displaystyle\lambda_{j}\cdot
x_{j}$ $\displaystyle\leq$ $\displaystyle 1\qquad\ \ \text{ for all }j\in[m].$
(4.3) $\displaystyle x_{j}$ $\displaystyle\geq$ $\displaystyle 0\qquad\ \
\text{ for all }j\in[m].$ (4.4)

Subsequently, the algorithm $\mathcal{A}^{*}$ performs the steps outlined in
Figure 11.

1. For All $b\in B$: 2. Set $\lambda_{j}=L:=m/k^{*}$ for all $j\in[m]$ with $b_{j}=0$, and feed these updates to $\mathcal{A}$. 3. If $\mathcal{A}$ returns an estimate $\nu\leq 2k^{*}$, then 4. Report that we are in case (1) of Problem 4.1, and terminate. 5. Return the LP to its initial state, by setting $\lambda_{j}=1$ for all $j\in[m]$ with $b_{j}=0$, and feeding these updates to the dynamic algorithm $\mathcal{A}$. 6. Report that we are in case (2) of Problem 4.1 and terminate.

Figure 11: Solving Problem 4.1 using the dynamic algorithm $\mathcal{A}$.

######  Claim 4.1.

Suppose that $a\cdot b\leq k^{*}$ for all $a\in A,b\in B$. Then the algorithm
$\mathcal{A}^{*}$ correctly reports that we are in case (2) of Problem 4.1.

###### Proof.

Consider any vector $b\in B$, and focus on the corresponding iteration of the
For loop in Figure 11. After step (2) of this iteration, we have
$\lambda_{j}=L$ for all $j\in[m]$ with $b_{j}=0$, and $\lambda_{j}=1$ for all
$j\in[m]$ with $b_{j}=1$. Now, define an $x$ where $x_{j}=1$ for all $j\in[m]$
with $b_{j}=1$, and $x_{j}=0$ for all $j\in[m]$ with $b_{j}=0$. Such an $x$ is
a feasible solution to the LP and has an objective of
$\sum_{j=1}^{m}x_{j}=\left|\\{j\in[m]:b_{j}=1\\}\right|=k$. This implies that
$\text{{\sc Opt}}\geq k$. Accordingly, in step (3), the dynamic algorithm
$\mathcal{A}$ returns a value
$\nu\geq\frac{k}{\beta}=\frac{3k}{\beta^{*}}=3k^{*}$. Hence, the algorithm
$\mathcal{A}^{*}$ does not terminate during this iteration.

The preceding discussion implies that $\mathcal{A}^{*}$ does not terminate
during any iteration of the For loop in Figure 11. Instead, at the end of the
For loop, it correctly reports that we are in case (2) of Problem 4.1. ∎

######  Claim 4.2.

Suppose that there exists vectors $a\in A,b\in B$ such that $a\geq b$. Then
the algorithm $\mathcal{A}^{*}$ correctly reports that we are in case (1) of
Problem 4.1.

###### Proof.

Focus on the iteration of the For loop in Figure 11 which deals with the
vector $b\in B$. After step (2) of this iteration, we have $\lambda_{j}=L$ for
all $j\in[m]$ with $b_{j}=0$, and $\lambda_{j}=1$ for all $j\in[m]$ with
$b_{j}=1$. Partition the set $[m]$ into two subsets:
$P_{0}=\\{j\in[m]:b_{j}=0\\}$ and $P_{1}=\\{j\in[m]:b_{j}=1\\}$. Since $a\geq
b$, we have $a_{j}=1$ for all $j\in P_{1}$. Let $x$ be any feasible solution
to LP (4.1). Observe that:

$\sum_{j\in P_{1}}x_{j}=\sum_{j\in P_{1}}a_{j}x_{j}\leq a\cdot x\leq k^{*}.$
(4.5)

Next, recall that $\lambda_{j}=L$ for all $j\in P_{0}$. Thus, we have
$x_{j}\leq 1/L$ for all $j\in P_{0}$, and hence:

$\sum_{j\in P_{0}}x_{j}\leq\frac{m}{L}=\kappa^{*}.$ (4.6)

Summing (4.5) and (4.6), we now get: $\sum_{j=1}^{m}x_{j}\leq 2k^{*}$. Since
this inequality holds for every feasible solution $x$ to the LP, we get
$\text{{\sc Opt}}\leq 2k^{*}$. Accordingly, during step (3) of the concerned
iteration of the For loop in Figure 11, the dynamic algorithm $\mathcal{A}$
returns a value $\nu\leq 2k^{*}$. Thus, the algorithm $\mathcal{A}^{*}$
terminates at this point, before correctly reporting that we are in case (1)
of Problem 4.1. ∎

The correctness of algorithm $\mathcal{A}^{*}$ follows from Claim 4.1 and
Claim 4.2. The claim below bounds its run time in terms of the update time of
the dynamic algorithm $\mathcal{A}$.

######  Claim 4.3.

The algorithm $\mathcal{A}^{*}$ runs in $\hat{O}(N\cdot T)$ time, where $T$ is
the update time of $\mathcal{A}$.

###### Proof.

The algorithm $\mathcal{A}^{*}$ starts by feeding LP (4.1), which is of
$\hat{O}(N)$ size, to $\mathcal{A}$ as input at pre-processing. Subsequently,
during each iteration $b\in B$ of the For loop, it feeds
$\Theta(m)=\hat{O}(1)$ updates to $\mathcal{A}$. Since the For loop runs for
at most $N$ iterations, overall the dynamic algorithm $\mathcal{A}$ needs to
handle at most $\hat{O}(N)$ updates. Hence, the total time spent by the
dynamic algorithm $\mathcal{A}$ is at most $\hat{O}(N\cdot T)$. The claims
follows since the runtime of $\mathcal{A}^{*}$ is dominated by the total
update time of $\mathcal{A}$. ∎

Theorem 4.2 implies that assuming SETH, the run time of algorithm
$\mathcal{A}^{*}$ must be $\Omega(N^{2-\epsilon})$ for every constant
$\epsilon>0$. Hence, from Claim 4.3 it follows that the amortized update time
of the dynamic algorithm $\mathcal{A}$ is at least $T=\Omega(N^{1-o(1)})$.
This concludes the proof of part-(i) of Theorem 4.3.

If we wish to prove the same lower bound for translation updates, then the
reduction remains almost the same. The only difference now is that in step (2)
of Figure 11, instead of changing the value of the coefficient $\lambda_{j}$
we now change the constraints $x_{j}\leq 1$ to $x_{j}\leq 0$ for the concerned
co-ordinates $j$, and un-do these changes in step (5) as before.

###  4.2 Proof of Theorem 4.3 \- part (ii)

We prove the theorem for packing LPs. The proof for covering LPs immediately
follows via LP duality.

As in Section 4.2, set $\beta:=\beta^{*}/3$. Suppose that there is a dynamic
algorithm $\mathcal{A}$ that maintains an estimate $\frac{\text{{\sc
Opt}}}{\beta}\leq\nu\leq\text{{\sc Opt}}$ for a packing LP undergoing
restricting entry updates in $\Theta(T)$ worst-case update time. Using
$\mathcal{A}$ as a subroutine, we design a static algorithm $\mathcal{A}^{*}$
for Problem 4.1. To achieve this goal, we follow almost exactly the same
strategy as in Section 4.2. The only difference being that in step (5) of
Figure 11, instead of feeding a new set of updates to $\mathcal{A}$, we roll
back the state of $\mathcal{A}$ to where it was at pre-processing. This allows
us to deal with the fact that $\mathcal{A}$ can only handle restricting (not
fully dynamic) updates. The rest of the arguments in the proof remain the same
as in Section 4.2.

The preceding discussion implies the desired lower-bound when the input LP
undergoes restricting updates. To derive the analogous lower-bound for
relaxing updates, we need to make only the following minor tweak in our design
of algorithm $\mathcal{A}^{*}$: Initially, we set $\lambda_{j}=L$ for all
$j\in[m]$. Subsequently, in step (2) of Figure 11, we set $\lambda_{j}=1$ for
all $j\in[m]$ with $b_{j}=1$, and feed these updates to $\mathcal{A}$. Next,
in step (5) of Figure 11, we roll back the state of $\mathcal{A}$ to where it
was at pre-processing.

Finally, we can easily extend our lower bounds to hold in settings where we
only have translation updates, using the idea outlined in the last paragraph
of Section 4.2.

##  Appendix A Proofs of Theorem 2.12 and Lemma 2.13

##### Proof of Lemma 2.13:

To conclude Lemma 2.13 notice that Lemma 2.9 seamlessly extends to the dynamic
setting. The only property of the dynamic input matrix $C$ the proof of Lemma
2.9 exploits is that at the time of the $t$-th Whack sub-routine it holds that
$(Cx^{t})_{i_{t}}<1$ which is similarly guaranteed in the dynamic setting. To
argue it formally let $C^{t}$ refer to the state of constraint matrix $C$ at
the time of the $t$-th Whack call. Fix some $t\in[T]$. The following line of
inequalities in analogous with the proof of Lemma 2.13.

$\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^{t}_{i_{t},j}}{\lambda}\right)=\frac{\epsilon}{\lambda}\cdot\left(C^{t}\hat{x}^{t}\right)_{i_{t}}<\frac{\epsilon}{\lambda}\cdot\left\lVert\hat{x}^{t}\right\rVert_{1}$

The last inequality follows since $\left(C^{t}x^{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}$

As $T=\frac{\lambda\ln(n)}{\epsilon^{2}}$ and
$\left\lVert\hat{x}^{0}\right\rVert_{1}=n$ we get the following:
$\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]$.

##### Proof of Theorem 2.12:

The extension of Theorem 2.6 to the dynamic setting is also relatively
straightforward. Observe, that at the initialization of our dynamic algorithm
we simply run the static implementation. Therefore before any update occurs
Theorem 2.12 can be concluded from Theorem 2.6. We will first argue that if
the dynamic algorithm returns vector $\tilde{x}^{t}$ then it must satisfy that
$C\cdot\tilde{x}^{t}\geq\mathbb{1}\cdot(1-\epsilon)$ and
$|\tilde{x}^{t}|_{1}\leq 1+\epsilon$ even after some restricting updates have
occurred.

Consider the starting point of a given phase at time $\tau$. At this point
$\mathbb{1}^{\top}\tilde{x}^{\tau}=\mathbb{1}^{\top}\hat{x}^{\tau}/\left\lVert\hat{x}^{\tau}\right\rVert_{1}=1$
and we fix $W=\left\lVert\hat{x}^{\tau}\right\rVert_{1}$. During the phase
$\tilde{x}^{t}$ may only monotonously increase. However, if at any point
$\left\lVert\hat{x}^{t}\right\rVert_{1}>(1-\epsilon/2)^{-1}\cdot W$ a new
phase begins. As $\tilde{x}^{t}=\hat{x}^{t}/W$ during the phase
$\left\lVert\tilde{x}^{t}\right\rVert_{1}\leq(1-\epsilon/2)^{-1}\leq
1+\epsilon$.

Fix some $i\in[m]$. At the start of each phase the algorithm ensures that
$(C\cdot\tilde{x}^{t})_{i}\geq 1$ through enforcing all currently violating
constraints. As during a phase $\tilde{x}^{t}$ may only monotonously increase
until further restricting updates occur to constraint $i$ it will remain
satisfied. At all times the algorithm keeps an $\epsilon$-approximate estimate
of $(C\cdot\tilde{x}^{t})$. Whenever a restricting update occurs to some
constraint element $C_{i,j}$ and we observe that out estimate of the
constraint value falls bellow $1$ we enforce constraint $i$ until
$(C\cdot\tilde{x}^{t})_{i}\geq 1$. Due to us keeping an $\epsilon$-approximate
estimate of $(C\cdot\tilde{x}^{t})_{i}$ this will never allow it to fall
bellow $1-\epsilon$. Note that the value of $(C\cdot\tilde{x}^{t})_{i}$ only
depends on the $i$-th row of $C$ and $\tilde{x}^{t}$ therefore if a
restricting update occurs to constraint $i$ and we decide not to enforce the
constraint itself then the values of all other constraints remain unaffected.

It remains to argue that whenever the dynamic algorithm returns vector $y$
following a series of updates it holds that $|y|_{1}=1$ and
$C^{\top}y\leq\mathbb{1}\cdot(1+4\cdot\epsilon)$. Once the algorithm has
returned such a vector $y$ it will no longer change its output. As $C$-s
elements may only get reduced over time $y$ will maintain these properties.
Here we refer to the proof of Lemma 2.2 with slight deviations. Recall the
experts setting from [AHK12] as presented in the proof Lemma 2.2. Further
recall the statement of Lemma 2.4.

We map the whack-a-mole algorithm to the experts setting in the same manner
however now accounting for the evolving constraint matrix. Let $C^{t}$ stand
for the state of $C$ at the time of the $t$-th call to Whack. 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^{t}_{i_{t},j}$.

Since $C^{t}_{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].$ (A.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].$ (A.2)

We next upper bound the right hand side (RHS) of (A.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(C^{t}x^{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 (A.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).$
(A.3)

We now focus our attention on the left hand side (LHS) of (A.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^{t})^{\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^{t})^{\top}y^{t}\right)_{j}\geq\frac{1}{T}\cdot\frac{1}{\lambda}\cdot\sum_{t=1}^{T}\left((C^{T})^{\top}y^{t}\right)_{j}=\frac{1}{\lambda}\cdot\left((C^{T})^{\top}y\right)_{j}.$
(A.4)

In A.4 the inequality holds as the elements of $C$ may only reduce over time.
The inequality is the most significant deviation from the proof in the static
setting. From (A.2), (A.3) and (A.4), we get:

$\frac{(1-\epsilon)}{\lambda}\cdot\left((C^{T})^{\top}y\right)_{j}\leq\frac{1}{\lambda}\cdot(1+\epsilon),\text{
and hence }\left((C^{T})^{\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
Theorem 2.12.

##  Appendix B Missing Proofs from Section 3.1

######  Claim B.1.

A coordinate $k$ is cheap if and only if $\langle\nabla
f_{p}(x),e_{k}\rangle\leq(1+\epsilon)\langle\nabla f_{c}(x),e_{k}\rangle$.

###### Proof.

Follows from definitions: $\langle\nabla
f_{p}(x),e_{k}\rangle=\frac{\sum_{i\in[m_{p}]}e^{\eta\cdot P_{i}x}\cdot
P(i,k)}{\sum_{i\in[m_{p}]}e^{\eta\cdot P_{i}x}}$, $\langle\nabla
f_{c}(x),e_{k}\rangle=\frac{\sum_{i\in[m_{c}]}e^{\eta\cdot C_{i}x}\cdot
C(i,k)}{\sum_{i\in[m_{c}]}e^{\eta\cdot C_{i}x}}$, hence if
$\frac{\langle\nabla f_{p}(x),e_{k}\rangle}{\langle\nabla
f_{c}(x),e_{k}\rangle}\leq 1+\epsilon$ we have that
$\frac{\sum_{i\in[m_{p}]}e^{\eta\cdot P_{i}x}\cdot
P(i,k)}{\sum_{i\in[m_{c}]}e^{\eta\cdot C_{i}x}\cdot
C(i,k)}\cdot\frac{\sum_{i\in[m_{c}]}e^{\eta\cdot
C_{i}x}}{\sum_{i\in[m_{p}]}e^{\eta\cdot
P_{i}x}}=\lambda(x,k)\cdot\frac{w_{c}(x)}{w_{p}(x)}\leq 1+\epsilon$.

∎

###  B.1 Proof of Property 3.3

###### Proof.

The proof is analogous to the argument of Young [You14]. Let $y$ be a feasible
solution to the linear program. Then we have that
$\frac{\sum_{i=1}^{m_{p}}(Cy)_{i}\cdot w_{c}(x,i)}{w_{c}(x)}\geq
1\geq\frac{\sum_{i=1}^{m_{p}}(Py)_{i}\cdot w_{p}(x,i)}{w_{p}(x)}$ as
$w_{c}(x,i)/w_{c}(x)$ and $w_{p}(x,i)/w_{p}(x)$ just are describing
distributions over the the constraints. This could be phrased as:

$y\cdot(C^{T}\cdot\frac{w_{c}(x)}{|w_{c}(x)|}-P^{T}\cdot\frac{w_{p}(x)}{|w_{p}(x)|})$

Which as $y$ is non-negative implies that there is an $i$ such that
$C_{i}^{T}\cdot\frac{w_{c}(x)}{|w_{c}(x)|}-P_{i}^{T}\cdot\frac{w_{p}(x)}{|w_{p}(x)|}\geq
0$ which is equivalent to saying $\lambda(x,i)\leq\frac{w_{p}(x)}{w_{c}(x)}$
meaning there is a cheap coordinate.

∎

###  B.2 Proof of Property 3.4

For the convenience of the reader we will restate the statement precisely:
given $\epsilon$ is sufficiently small such that $\epsilon\leq 1/10$ we have
that:

$f_{p}(x+\delta\cdot
e_{k})-f_{p}(x)\leq(1+10\cdot\epsilon)\cdot(f_{c}(x+\delta\cdot
e_{k})-f_{c}(x))\leq(1+10\cdot\epsilon)\cdot\epsilon\leq 2\cdot\epsilon$

###### Proof.

Note, that if $\epsilon\leq 1/10$ then $exp(-\log(m_{c}+U/L)/\epsilon)\leq
exp(-2\cdot\ln(m_{c}+U/L)-1/\epsilon+2)\leq\frac{\epsilon\cdot L}{U\cdot
m_{c}}$.

Let $k$ be a cheap coordinate which the algorithms boosts by $\delta$ and let
$x$ stand for the value of the output vector before boosting. If coordinate
$k$ is boosted we have that $\langle\nabla
f_{p}(x),e_{k}\rangle\leq(1+\epsilon)\cdot\langle\nabla
f_{c}(x),e_{k}\rangle$. We will show that $\langle\nabla f_{p}(x+\delta\cdot
e_{k}),e_{k}\rangle\leq\langle\nabla
f_{p}(x),e_{k}\rangle\cdot(1+O(\epsilon))$ and $\langle\nabla
f_{c}(x+\delta\cdot e_{k}),e_{k}\rangle\geq\langle\nabla
f_{p}(x),e_{k}\rangle\cdot(1-O(\epsilon))$. As $f_{c}(x)$ and $f_{p}(x)$
monotonously reduces and increases respectively with $x$ this implies that
during the boost it must hold that $\langle\nabla
f_{p}(x),e_{k}\rangle\leq(1+O(\epsilon))\cdot\langle\nabla
f_{c}(x),e_{k}\rangle$ which in turn implies that $f_{p}(x+\delta\cdot
e_{k})-f_{p}(x)\leq(f_{c}(x+\delta\cdot e_{k})-f_{c}(x))\cdot(1-O(\epsilon))$
implying one half of the claim.

$\displaystyle\langle\nabla f_{p}(x+\delta\cdot e_{k}),e_{k}\rangle$
$\displaystyle=$ $\displaystyle\frac{\sum_{i\in[m_{p}]}e^{\eta\cdot
P_{i}(x+\delta\cdot e_{k})}\cdot P(i,k)}{\sum_{i\in[m_{p}]}e^{\eta\cdot
P_{i}(x+\delta\cdot e_{k})}}$ $\displaystyle\leq$
$\displaystyle\frac{\sum_{i\in[m_{p}]}e^{\epsilon+\eta\cdot P_{i}x}\cdot
P(i,k)}{\sum_{i\in[m_{p}]}e^{\eta\cdot P_{i}x}}$ $\displaystyle=$
$\displaystyle e^{\epsilon}\cdot\langle\nabla f_{p}(x),e_{k}\rangle$
$\displaystyle\leq$ $\displaystyle(1+2\cdot\epsilon)\cdot\langle\nabla
f_{p}(x),e_{k}\rangle$ (B.2)

Inequality B.2 follows from the definition of $\delta$ and Inequality B.2
applies for any $\epsilon\leq 1$.

Define $I=\\{i\in[m_{c}]:C_{i}x>2$ and $A=\\{i\in[m_{c}]:C_{i}x\leq 2\\}$
representing the inactive and active constraints of $C$.

$\displaystyle\langle\nabla f_{c}(x),e_{k}\rangle$ $\displaystyle=$
$\displaystyle\frac{\sum_{i\in[m_{c}]}e^{-\eta\cdot C_{i}x}\cdot
C(i,k)}{\sum_{i\in[m_{c}]}e^{-\eta\cdot C_{i}x}}$ (B.3) $\displaystyle=$
$\displaystyle\frac{\sum_{i\in A}e^{-\eta\cdot C_{i}x}\cdot C(i,k)+\sum_{i\in
I}e^{-\eta\cdot C_{i}x}\cdot C(i,k)}{\sum_{i\in A}e^{-\eta\cdot
C_{i}x}+\sum_{i\in I}e^{-\eta\cdot C_{i}x}}$ $\displaystyle\leq$
$\displaystyle\frac{\sum_{i\in A}e^{-\eta\cdot C_{i}x}\cdot C(i,k)+\sum_{i\in
I}e^{-\eta\cdot C_{i}x}\cdot C(i,k)}{\sum_{i\in A}e^{-\eta\cdot C_{i}x}}$
$\displaystyle\leq$ $\displaystyle\frac{\sum_{i\in A}e^{-\eta\cdot
C_{i}x}\cdot C(i,k)+\sum_{i\in I}e^{-2\cdot\eta}\cdot C(i,k)}{\sum_{i\in
A}e^{-\eta\cdot C_{i}x}}$ $\displaystyle\leq$ $\displaystyle\frac{\sum_{i\in
A}e^{-\eta\cdot C_{i}x}\cdot C(i,k)+e^{-\eta}\cdot m_{c}\cdot
e^{-\frac{\log(m_{c}+U/L)}{\epsilon}}\cdot\max_{i\in[m_{c}]}\\{C(i,k)\\}}{\sum_{i\in
A}e^{-\eta\cdot C_{i}x}}$ $\displaystyle\leq$ $\displaystyle\frac{\sum_{i\in
A}e^{-\eta\cdot C_{i}x}\cdot C(i,k)+e^{-\eta}\cdot L\cdot\epsilon}{\sum_{i\in
A}e^{-\eta\cdot C_{i}x}}$ $\displaystyle\leq$ $\displaystyle\frac{\sum_{i\in
A}e^{-\eta\cdot C_{i}x}\cdot C(i,k)}{\sum_{i\in A}e^{-\eta\cdot
C_{i}x}}\cdot(1+\epsilon)$ (B.4)

Equation B.3 follows if $\epsilon$ is selected small enough such that
$e^{-\frac{\log(m_{c}+U/L)}{\epsilon}}\leq\frac{\epsilon\cdot L}{U\cdot
m_{c}}$. Equation B.4 follows from the fact that in order for a boost to occur
there must be at least one unsatisfied covering constraint, hence $\sum_{i\in
A}e^{-\eta\cdot C_{i}x}\cdot C(i,k)\geq e^{-\eta}\cdot L$.

$\displaystyle\langle\nabla f_{c}(x+\delta\cdot e_{i}),e_{k}\rangle$
$\displaystyle=$ $\displaystyle\frac{\sum_{i\in[m_{c}]}e^{-\eta\cdot
C_{i}(x+\delta\cdot e_{i})}\cdot C(i,k)}{\sum_{i\in[m_{c}]}e^{-\eta\cdot
C_{i}(x+\delta\cdot e_{i})}}$ (B.5) $\displaystyle=$
$\displaystyle\frac{\sum_{i\in A}e^{-\eta\cdot C_{i}(x+\delta\cdot
e_{i})}\cdot C(i,k)+\sum_{i\in I}e^{-\eta\cdot C_{i}(x+\delta\cdot
e_{i})}\cdot C(i,k)}{\sum_{i\in A}e^{-\eta\cdot C_{i}(x+\delta\cdot
e_{i})}+\sum_{i\in I}e^{-\eta\cdot C_{i}(x+\delta\cdot e_{i})}}$
$\displaystyle\geq$ $\displaystyle\frac{\sum_{i\in A}e^{-\eta\cdot
C_{i}(x+\delta\cdot e_{i})}\cdot C(i,k)}{\sum_{i\in A}e^{-\eta\cdot
C_{i}(x+\delta\cdot e_{i})}+\sum_{i\in P}e^{-\eta\cdot C_{i}(x+\delta\cdot
e_{i})}}$ $\displaystyle\geq$ $\displaystyle\frac{\sum_{i\in A}e^{-\eta\cdot
C_{i}(x+\delta\cdot e_{i})}\cdot C(i,k)}{\sum_{i\in A}e^{-\eta\cdot
C_{i}(x+\delta\cdot e_{i})}+m_{c}\cdot e^{-2\cdot\eta}}$ $\displaystyle\geq$
$\displaystyle\frac{\sum_{i\in A}e^{-\eta\cdot C_{i}(x+\delta\cdot
e_{i})}\cdot C(i,k)}{\sum_{i\in A}e^{-\eta\cdot C_{i}(x+\delta\cdot
e_{i})}}\cdot\frac{1}{1+\epsilon}$ $\displaystyle\geq$
$\displaystyle\frac{\sum_{i\in A}e^{-\eta\cdot C_{i}x}\cdot C(i,k)}{\sum_{i\in
A}e^{-\eta\cdot C_{i}x}}\cdot\frac{e^{-\epsilon}}{1+\epsilon}$ (B.6)

Here Equation B.5 similarly follows from the fact that $\sum_{i\in
A}e^{-\eta\cdot C_{i}(x+\delta\cdot e_{i})}\geq e^{-\eta-\epsilon}$ (by the
choice of $\delta$) and by the definition of $\eta$. Equation B.6 follows from
the definition of $\delta$. Therefore, we get that $\langle\nabla
f_{c}(x+\delta\cdot
e_{i}),e_{k}\rangle\cdot(1+4\cdot\epsilon)\geq\langle\nabla
f_{c}(x+\delta\cdot
e_{i}),e_{k}\rangle\cdot{\frac{(1+\epsilon)^{2}}{e^{-\epsilon}}}\geq\langle\nabla
f_{c}(x),e_{k}\rangle$ (given $\epsilon<1/5$).

As $\langle\nabla f_{p}(x+\delta\cdot
e_{i}),e_{k}\rangle\leq(1+2\cdot\epsilon)\langle\nabla f_{p}(x),e_{k}\rangle$
and $\langle\nabla f_{p}(x),e_{k}\rangle\leq\langle\nabla
f_{x}(x),e_{k}\rangle\cdot(1+\epsilon)$ we have that $\langle\nabla
f_{p}(x+\delta\cdot e_{i}),e_{k}\rangle\leq\langle\nabla f_{c}(x+\delta\cdot
e_{i}),e_{k}\rangle\cdot(1+\epsilon)\cdot(1+2\cdot\epsilon)\cdot(1+4\epsilon)\leq\langle\nabla
f_{c}(x+\delta\cdot e_{i}),e_{k}\rangle\cdot(1+10\cdot\epsilon)$ (given
$\epsilon\leq 1/10$).

As both $f_{c}(x)$ and $f_{p}(x)$ are monotone in $x$ we get that
$f_{p}(x+\delta\cdot e_{k})-f_{p}(x)\leq(f_{c}(x+\delta\cdot
e_{k})-f_{c}(x))\cdot(1+10\cdot\epsilon)$. Note that
$f_{c}(x)\geq\min_{i\in[m_{c}]}C_{i}x$ and $f_{c}(x+\delta\cdot
e_{k})+\epsilon\leq\min_{i\in[m_{c}]}C_{i}(x+e_{k}\cdot\epsilon)\leq\min_{i\in[m_{c}]}C_{i}x+\epsilon$
therefore $f_{c}(x+\delta\cdot e_{k})-f_{c}(x)\leq\epsilon$. Therefore, we can
conclude the original inequality.

∎

##  Appendix C Complete Algorithm from Section 3.2

In Section 3, we presented an overview of our dynamic algorithm for positive
LPs under relaxing updates. But we glossed over some implementation details to
highlight the key ideas. For instance, we did not specify the dynamic data
structure that will be needed to find the appropriate $\delta$ during a call
to the Boost$(x,k)$ subroutine (see step 1 in Figure 9). Furthermore, in
Section 3.2.2 we focused only on relaxing updates to the covering constraints,
and we sketched in Section 3.2.3 how to deal with the relaxing updates to the
packing constraints. Accordingly, to address these gaps, in this section we
present a full, comprehensive version of our dynamic algorithm for positive
LPs under relaxing updates.

##### Preliminaries:

Let $P\in\Re_{\geq 0}^{m_{p}\times n}$ and $C\in\Re_{\geq 0}^{m_{c}\times n}$
be input matrices to the linear program. Let $N$ stand for the number of
entries in $P$ and $C$ which are non-zero at any point during the run of the
algorithm. Let $U$ and $L$ stand for upper and lower bounds on the elements of
the constraint matrices $P$, $C$ at all times, respectively. Let $t$ stands
for the total number of relaxing updates progressed by the dynamic algorithm.

Let $R^{P}_{i}:i\in[m_{p}]$, $R^{C}_{j}:j\in[m_{c}]$ refer to the number of
elements in the $i$-th row of $P$ and the $j$-th row of $C$ respectively which
take a non-zero value at any time. Similarly, define $N^{P}_{k}:k\in[n]$ and
$N^{C}_{k}:k\in[n]$ to represent the number of elements in the $k$-th column
of $P$ and $C$ respectively taking a non-zero value at any point.

######  Theorem C.1.

There is an algorithm for maintaining a certificate of infeasability or
returning an $\epsilon$-approximate solution for a relaxing dynamic positive
linear program in $O(\frac{N\cdot\log^{2}(m_{p}+m_{c}+U/L)}{\epsilon^{2}}+t)$
deterministic time (for $\epsilon<1/200$).

We will dedicate this entire section to proving Theorem C.1. For sake of
simplicity we will first show how we can handle a dynamic linear program
undergoing solely entry wise updates. In Subsection C.6 we will show to extend
the algorithm for translation updates. We will make the following assumption
on the distribution of inputs:

######  Assumption C.2.

Non-zero elements of input matrices $P$ and $C$ lie in the range of
$[1/poly(N),poly(N)]$ at all times.

###  C.1 Variables

Define $P^{*}$, $C^{*}$ and $X^{*}$ as described in Section 3.2.3:

  * •

$P^{*}\in\mathbb{R}_{\geq 0}^{m_{p}\times(n+1)}$, where $P^{*}(i,k)=P(i,k)$
and $P^{*}(i,n+1)\geq 0$ for all $i\in[m_{p}],k\in[n]$.

  * •

$C^{*}\in\mathbb{R}_{\geq 0}^{m_{c}\times(n+1)}$, where $C^{*}(j,k)=C(j,k)$
and $C^{*}(j,n+1)=0$ for all $j\in[m_{c}],k\in[n]$.

  * •

$x^{*}\in\mathbb{R}_{\geq 0}^{n+1}$ and $x$ refers to the first $n$
coordinates of $x^{*}$

From now on we will refer to the linear program defined by $Px\leq\mathbb{1}$,
$CX\geq\mathbb{1}$ as the original linear program and to the linear program
defined by $P^{*}x^{*}\leq\mathbb{1}$, $C^{*}x^{*}\geq\mathbb{1}$ as the
extended linear program. Use variable $i$ and $j$ to refer to row indices of
$P$ and $C$ respectively, and use $k$ for referring to column indices of $P$
or $C$.

######  Observation C.3.

If $x$ is a feasible solution to the original linear program then $\\{x,1\\}$
($x$ extended with a $1$) is a valid solution to the extended linear program.
If $x^{*}$ is a feasible solution to the extended linear program then the
first $n$ coordinates of $x^{*}$ form a feasible solution to the original
linear program. Hence, the original linear program is feasible if and only if
the extended linear program is feasible.

Due to Observation C.3 we will focus only on the extended linear program in
this section.

##### Data-Structure:

We will initially define the following variables:

$\eta=\frac{\log(m_{c}+m_{p}+U/L)}{\epsilon}$ (C.1)

  * •

$w_{c}(x^{*},i)=1$ for $i\in[m_{c}]$ representing covering constraint weights

  * •

$w_{p}(x^{*},j)=1$ for $j\in[m_{p}]$ representing packing constraint weights

  * •

$w_{c}(x^{*})=\sum_{i\in[m_{c}]}w_{c}(x^{*},i)$ and
$w_{p}(x^{*})=\sum_{j\in[m_{p}]}w_{p}(x^{*},j)$

  * •

$\lambda(x^{*})_{0}=\frac{w_{p}(x^{*})}{w_{c}(x^{*})}$

For the purposes of the analysis we will define $\lambda(x^{*},k)=\forall
k\in[n]:\lambda(x^{*},k)=\frac{\sum_{j\in[m_{p}]}w_{p}(x^{*},j)\cdot
P^{*}(j,k)}{\sum_{i\in[m_{c}]}w_{c}(x^{*},i)\cdot C^{*}(i,k)}$ representing
the price of each coordinate. Note that after initialization the algorithm
will not keep track of exact $\lambda(x^{*},k)$ values. Similarly, for the
purposes of the algorithm description and analysis define but do not maintain

$\forall
k\in[n]:\delta_{k}=\max_{\delta}\\{\max\\{\max_{i\in[m_{p}]}P^{*}(i,k)\cdot\delta,\max_{j\in[m_{c}]|C^{*}_{j}x^{*}<2}C^{*}(j,k)\cdot\delta\\}=\epsilon/\eta\\}$

##### Approximate Variables:

The algorithm will initialize the following approximate variables:

  * •

$\forall i\in[m_{p}]:\hat{w_{p}}(x^{*},i)=w_{p}(x^{*},i)$

  * •

$\forall j\in[m_{c}]:\hat{w_{c}}(x^{*},j)=w_{c}(x^{*},j)$

  * •

$\hat{w}_{p}(x^{*})=w_{p}(x^{*})$

  * •

$\hat{w}_{c}(x^{*})=w_{c}(x^{*})$

  * •

$\forall k\in[n]:\hat{\lambda}(x^{*},k)=\lambda(x^{*},k)$

  * •

$\hat{\lambda}_{0}(x^{*})=\lambda_{0}(x^{*})$

######  Invariant C.4.

The following inequalities are simultaneously satisfied:

  * •

$\forall i\in[m_{c}]:w_{c}(x^{*},i)\leq\hat{w_{c}}(x^{*},i)\leq
w_{c}(x^{*},i)\cdot(1+\epsilon)$

  * •

$\forall i\in[m_{p}]:w_{p}(x^{*},i)\geq\hat{w_{p}}(x^{*},i)\geq
w_{p}(x^{*},i)\cdot(1-\epsilon)$

  * •

$\forall
k\in[n]:\hat{\lambda}(x^{*},k)=\frac{\sum_{j\in[m_{p}]}\hat{w_{p}}(x^{*},j)\cdot
P^{*}(j,k)}{\sum_{i\in[m_{c}]}\hat{w_{c}}(x^{*},i)\cdot C^{*}(i,k)}$ and
$\hat{\lambda}_{0}(x^{*})\geq\lambda_{0}(x^{*})\cdot(1-\epsilon)$

###  C.2 Algorithm

#####  Iterate subroutine:

Initially the algorithm calls the Iterate() sub-routine which initializes
$\hat{\lambda}_{0}(x^{*})=\lambda_{0}(x^{*})$ and iterates over all
coordinates $k\in[n]$. Iterate() boosts any coordinate $k$ satisfying
$\hat{\lambda}(x^{*},k)\leq\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$ until
$\hat{\lambda}(x^{*},k)>\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$. If due to
the boosts $\lambda_{0}(x^{*})$ has increased enough such that
$\lambda_{0}(x^{*})\cdot(1-\epsilon)>\hat{\lambda}_{0}(x^{*})$ Iterate() is
called recursively.

#####  Boost subroutine:

A call to Boost($k$) increases the $k$-th coordinate of $x^{*}$. The algorithm
selects an increment of $\delta$ such that all packing constraints and all not
’well’ satisfied covering constraints are increased by at most
$\epsilon/\eta$, that is
$\delta=\max_{\delta}\\{\max\\{\max_{i}P*(i,k)\cdot\delta,\max_{j|C^{*}_{j}<2}C^{*}(j,k)\cdot\delta\\}=\epsilon/\eta\\}$.
The algorithm increments $x^{*}$ by $e_{k}\cdot\delta$ and afterwards proceeds
to restore the affected variables
$w_{c}(x^{*},i),w_{p}(x^{*},j),w_{c}(x^{*}),w_{p}(x^{*})$ and
$\lambda_{0}(x^{*})$ precisely. Afterwards UpdatePWeights, UpdateCWeights
subroutines are called to ensure the correctness of Invariant C.4.

#####  UpdatePweights, UpdateCWeights subroutines:

These subroutines are used to update $\hat{w_{p}},\hat{w_{c}}$ and
$\hat{\lambda}$ values respectively. Without loss of generality assume that
UpdateCWeights($k$) was called. The algorithm checks for all $i\in[m_{P}]$
such that the $i$-th element of the $k$-th column of $P^{*}$ is not empty
($P*(i,k)>0$) weather $\hat{w}_{p}(x^{*},i)<w_{p}(x^{*},i)\cdot(1-\epsilon)$
as these are the $w_{p}(x^{*},i)$ values which have increased due to the
boosting coordinate $k$. For rows where the slack between the approximate and
actual values became too significant the algorithm readjusts the approximate
parameter ($\hat{w}_{p}(x^{*},i)\leftarrow w_{p}(x^{*},i)$) and adjusts all
values of $\hat{\lambda}(x^{*},k^{\prime})$ which might have been affected by
this change (that is the ones corresponding to columns of $P^{*}$ where the
$i$-th row is non empty, that is $P^{*}(i,k^{\prime})>0$).

#####  UpdateP subroutine:

A call UpdateP($i,k,\Delta$) handles a reduction of $\Delta$ to $P^{*}(i,k)$.
After updating $P*(i,k)$ the algorithm increments $P*(i,n+1)$ with
$\Delta\cdot x^{*}_{i}$ to guarantee that $w_{p}(x^{*},i)$ remains the same
after increasing $P^{*}(i,k)$. This way the only $\hat{\lambda}$ value which
is affected is $\hat{\lambda}(x^{*},k)$ which the subroutine updates to ensure
the correctness of Invariant C.4. Due to the update of
$\hat{\lambda}(x^{*},k)$ coordinate $k$ might become cheap (that is
$\hat{\lambda}(x^{*},k)\leq\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$) so the
subroutine boosts $k$ until it is no longer cheap. If some boosts occur then
$\lambda_{0}(x^{*})$ might reduce enough such that
$\hat{\lambda}_{0}(x^{*})<\lambda_{0}(x^{*})\cdot(1-\epsilon)$ in which case a
new call to Iterate is made to ensure the correctness of Invariant C.4.

1

2

Input: $C^{*}\in\Re_{\geq 0}^{m_{c}\times n},P^{*}\in\Re_{\geq 0}^{m_{p}\times
n}$

Output: $x^{*}\in\Re_{\geq
0}^{n+1}|C^{*}x^{*}\geq\mathbb{1},P^{*}x^{*}\leq\mathbb{1}\cdot(1+200\cdot\epsilon)$

3

4

5

6 Function  _Iterate(__)_ :

7 $\hat{\lambda}_{0}(x^{*})\leftarrow\lambda_{0}(x^{*})$

8 for  _$k\in[n]$_ do

9 while
_$\hat{\lambda}(x^{*},k)\leq\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$_ do

Boost(k)

// See Algorithm 2

10

11

12 if  _$\hat{\lambda}_{0}(x^{*}) <\lambda_{0}(x^{*})\cdot(1-\epsilon)$_ then

13 Iterate()

14

15

16 Function  _Main(__)_ :

17 Iterate()

18

19

Algorithm 1 Main subroutine of the algorithm

1

2

3

4

5 Function  _Boost(_k_)_:

$\delta\leftarrow$ sample in $[\delta_{k}/4,\delta_{k}]$

// See Section C.5

$x^{*}\leftarrow x^{*}+e_{k}\cdot\delta$

// $e_{k}$ is the unit $k$-th coordinate vector

6 if  _$C^{*}x^{*}\geq\mathbb{1}$_ then

7 Return $x^{*}$

8

9 for  _$\forall i\in[m_{p}]|P^{*}(i,k) >0$_ do

10 $w_{p}(x^{*},i)\leftarrow\exp(\eta\cdot P^{*}_{i}x^{*})$

11

$w_{p}(x^{*})\leftarrow\sum_{i\in[m_{p}]}w_{p}(x^{*},i)$

// Updated in $O(N^{P}_{k})$ time

12 for  _$\forall j\in[m_{c}]|C^{*}(j,k) >0$_ do

13 $w_{c}(x^{*},j)\leftarrow\exp(-\eta\cdot C^{*}_{j}x^{*})$

14

$w_{c}(x^{*})\leftarrow\sum_{j\in[m_{c}]}w_{c}(x^{*},j)$

// Updated in $O(N^{C}_{k})$ time

15 $\lambda_{0}(x^{*})=\frac{w_{p}(x^{*})}{w_{c}(x^{*})}$

UpdatePWeights(k)

// See Algorithm 3

UpdateCWeights(k)

// See Algorithm 4

16

17

Algorithm 2 Boosting of coordinate $k$

1

2

3

4

5 Function  _UpdatePWeights(_k_)_:

6 for  _$j\in[m_{p}]|P^{*}_{j,k} >0$_ do

7 if  _$\hat{w_{p}}(x^{*},j) <w_{p}(x^{*},j)\cdot(1-\epsilon)$_ then

8 $\hat{w_{p}}(x^{*},j)=w_{p}(x^{*},j)$

9 for  _$k^{\prime}\in[n]|P^{*}_{j,k^{\prime}} >0$_ do

10
$\hat{\lambda}(x^{*},k^{\prime})=\frac{\sum_{j^{\prime}\in[m_{p}]}\hat{w_{p}}(x^{*},j^{\prime})\cdot
P^{*}(j^{\prime},k^{\prime})}{\sum_{i\in[m_{c}]}\hat{w_{c}}(x^{*},i)\cdot
C^{*}(i,k^{\prime})}$

11

12

13

14

Algorithm 3 The subroutine updating packing weights

1

2

3

4

5 Function  _UpdateCWeights(_i_)_:

6 for  _$i\in[m_{c}]|C^{*}_{i,k} >0$_ do

7 if  _$\hat{w_{c}}(x^{*},i) >w_{c}(x^{*},i)\cdot(1+\epsilon)$_ then

8 $\hat{w_{c}}(x^{*},i)=w_{c}(x^{*},i)$

9 for  _$k^{\prime}\in[n]|C^{*}_{i,k^{\prime}} >0$_ do

10
$\hat{\lambda}(x^{*},k^{\prime})=\frac{\sum_{j\in[m_{p}]}\hat{w_{p}}(x^{*},j)\cdot
P^{*}(j,k^{\prime})}{\sum_{i^{\prime}\in[m_{c}]}\hat{w_{c}}(x^{*},i^{\prime})\cdot
C^{*}(i^{\prime},k^{\prime})}$

11

12

13

14

Algorithm 4 The subroutine updating covering weights

Input: $(j,k,\Delta)$: $P^{*}(j,k)$ decreased by $\Delta$

1

2 Function  _UpdateP(_$j,k,\Delta$_)_:

3 $P^{*}(i,k)\leftarrow P^{*}(i,k)-\Delta$

4 $P^{*}(i,n+1)=P^{*}(i,n+1)+\Delta\cdot x^{*}_{i}$

$\hat{\lambda}(x^{*},k)=\frac{\sum_{i^{\prime}\in[m_{p}]}\hat{w_{p}}(x^{*},i^{\prime})\cdot
P^{*}(i^{\prime},k)}{\sum_{j\in[m_{c}]}\hat{w_{c}}(x^{*},j)\cdot C^{*}(j,k)}$

// Updated in $O(1)$ time

5 while
_$\hat{\lambda}(x^{*},k)\leq\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$_ do

Boost($k$)

// See Algorithm 2

6

7

8 if  _$\hat{\lambda}_{0}(x^{*}) <\lambda_{0}(x^{*})\cdot(1-\epsilon)$_ then

Iterate()

// See Algorithm 1

9

10

11

Algorithm 5 Subroutine handling updates to the packing constraint matrix
$P^{*}$

1

Input: $(j,k,\Delta)$: $C^{*}(j,k)$ increased by $\Delta$

2

3

4 Function  _UpdateC(_$j,k,\Delta$_)_:

5

6 $C^{*}(j,k)\leftarrow C^{*}(j,k)+\Delta$

7

8 if  _$C^{*}x^{*}\geq\mathbb{1}$_ then

9 Return $x^{*}$

10

11

12 $w_{c}(x^{*},j)\leftarrow\exp(-\eta\cdot C^{*}_{j}x^{*})$

$w_{c}(x^{*})\leftarrow\sum_{j\in[m_{c}]}w_{c}(x^{*},j)$

// Updated in $O(1)$ time

13 $\lambda_{0}(x^{*})=\frac{w_{p}(x^{*})}{w_{c}(x^{*})}$

14 if  _$w_{c}(x^{*},j) <\hat{w_{c}}(x^{*},j)\cdot(1-\epsilon)$_ then

15 $\hat{w_{c}}(x^{*},j)=w_{c}(x^{*},j)$

16 for  _$k^{\prime}\in[n]|C^{*}_{j,k^{\prime}} >0$_ do

17
$\hat{\lambda}(x^{*},k^{\prime})=\frac{\sum_{i\in[m_{p}]}\hat{w_{p}}(x^{*},i)\cdot
P^{*}(i,k^{\prime})}{\sum_{j^{\prime}\in[m_{c}]}\hat{w_{c}}(x^{*},j^{\prime})\cdot
C^{*}(j^{\prime},k^{\prime})}$

18

19 for  _$k^{\prime}\in[n]|C^{*}_{j,k^{\prime}} >0$_ do

20 while
_$\hat{\lambda}(x^{*},k^{\prime})\leq\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$_
do

Boost(k’)

// See Algorithm 2

21

22

23

24 $\hat{\lambda}(x^{*},k)=\frac{\sum_{i\in[m_{p}]}\hat{w_{p}}(x^{*},i)\cdot
P^{*}(i,k)}{\sum_{j^{\prime}\in[m_{c}]}\hat{w_{c}}(x^{*},j^{\prime})\cdot
C^{*}(j^{\prime},k)}$

25 while
_$\hat{\lambda}(x^{*},k)\leq\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$_ do

Boost($k$)

// See Algorithm 2

26

27 if  _$\hat{\lambda}_{0}(x^{*}) <\lambda_{0}(x^{*})\cdot(1-\epsilon)$_ then

Iterate()

// See Algorithm 1

28

29

30

Algorithm 6 Subroutine handling updates to the covering constraint matrix
$C^{*}$

###  C.3 Correctness

######  Claim C.1.

Invariant C.4 is always satisfied by Algorithm 1.

###### Proof.

At initialization the invariant clearly holds by the definition of the
approximate variables as their exact counterparts. To prove the correctness of
the invariant we will consider the three instances where variables are updated
and argue inductively that they preserve Invariant C.4.

#####  Boost subroutine (Algorithm 2):

when Boost($k$) is called then elements of $w_{p}(x^{*},i)|P^{*}(i,k)>0$ and
$w_{p}(x^{*},j)|C^{*}(j,k)>0$, $w_{c}(x^{*})$, $w_{p}(x^{*})$ and
$\lambda_{0}(x^{*})$ are updated. Afterwards UpdatePWeights($k$) and
UpdateCWeights($k$) are called. These subroutines check variables
$\hat{w}_{p}(x^{*},i)|P^{*}(i,k)>0$ and $\hat{w}_{p}(x^{*},j)|C^{*}(j,k)>0$
and update them to enforce the requirements of Invariant C.4. Boost($k$) might
be called by subroutines Iterate, UpdateP and UpdateC. Each of these
subroutines call Iterate if the last requirement of Invariant C.4
($\hat{\lambda}_{0}(x^{*})<\lambda_{0}\cdot(1-\epsilon)$ is violated. As
Invariant C.4 can’t compile (as it calls itself) until
$\hat{\lambda}_{0}(x^{*})\geq\lambda_{0}\cdot(1-\epsilon)$ all of Invariant
C.4 will be satisfied after a boost operation.

#####  UpdateP subroutine (Algorithm 3):

UpdateP($i,k,\Delta$) doesn’t affect constraint weights by define. The only
variable it needs to update is $\hat{\lambda}(x^{*},k)$ because of the change
in $P^{*}(i,k)$. As argued previously, Invariant C.4 is restored by the Boost
calls inside of UpdateP.

#####  UpdateC subroutine (Algorithm 4):

UpdateC makes changes to $w_{c}(x^{*},j),w_{c}(x^{*})$ and
$\lambda_{0}(x^{*})$ and updates the approximate variables accordingly to fit
Invariant C.4. As argued previously the invariant is restored after proceeding
Boost calls.

∎

######  Claim C.2.

Whenever the algorithm halts without returning an answer the extended LP is
infeasible.

###### Proof.

By Claim C.1 we can assume that Invariant C.4 is satisfied whenever the
algorithm halts without returning an answer. Following the proof of Property
3.3 from Section B.1 if at any time for all $k\in[n]$ we have that
$\lambda(x^{*},k)<\lambda_{0}(x^{*})$ then the linear program is infeasible.
We will argue that Invariant C.4 implies $\forall
k\in[n]:\lambda(x^{*},k)<\lambda_{0}(x^{*})$. Fix $k\in[n]$ for this proof.

By Invariant C.4 we always have that
$\hat{\lambda}(x^{*},k)\geq\lambda(x^{*},k)$. Say whenever the algorithm
checked if
$\hat{\lambda}(x^{*},k)\leq\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$ that the
algorithm has checked the price of coordinate $k$. After a coordinates price
is checked it is boosted until
$\lambda(x^{*},k)\geq\hat{\lambda}(x^{*},k)>\lambda_{0}(x^{*})\cdot(1+5\cdot\epsilon)$.
Each coordinates price is checked at least once at initialization. Let
$\lambda_{0}^{-}(x^{*})$ and $\lambda_{0}^{+}(x^{*})$ represent the value of
$\lambda_{0}(x^{*})$ after the last time coordinate $k$-s price was checked
and at compilation respectively. Let $\hat{\lambda}_{0}(x^{*})^{*}$ represent
the value of $\hat{\lambda}_{0}(x^{*})$ at both of these time points (note
that if $\hat{\lambda}_{0}(x^{*})$ would have been updated between the last
price checking of coordinate $k$ and compilation a new call to Iterate() would
have been made, hence $k$-s price would have been checked again). By Invariant
C.4 we have that $\hat{\lambda}_{0}(x^{*})^{*}\leq\lambda_{0}^{-}(x^{*})$ and
$\hat{\lambda}_{0}(x^{*})^{*}\geq\lambda_{0}^{+}(x^{*})\cdot(1-\epsilon)$.
Therefore,
$\lambda_{0}^{+}(x^{*})\leq\frac{\lambda_{0}^{+}(x^{*})}{1-\epsilon}$.

$\lambda(x^{*},k)$-s value might only have reduced since the last time $k$-s
price was checked as at every instance it’s price might increase it is
checked. Therefore, we have that at that whenever the algorithm halts
$\lambda(x^{*},k)\geq\lambda_{0}(x^{*})\cdot(1+5\epsilon)\cdot(1-\epsilon)\geq\lambda_{0}(x^{*})$
if $\epsilon\leq 4/5$ which concludes the claim.

∎

######  Claim C.3.

At all times the algorithm satisfies that
$P^{*}x^{*}\leq\mathbb{1}\cdot(1+200\cdot\epsilon)$ (given $\epsilon<1/10$).

###### Proof.

We will show that the following invariant is maintained throughout the run of
algorithm:

$\max_{i\in[m_{p}]}\\{P^{*}_{i}x^{*}\\}\leq\min_{i\in[m_{c}]}\\{C^{*}_{i}x^{*}\\}\cdot(1+50\epsilon)+100\epsilon$

Initially the inequality holds and the inequality will be affected by 3 kinds
of changes: updates to $P^{*}$, $C^{*}$ and $x^{*}$. Notice, that whenever
$C^{*}$ is updated only the right hand size of the inequality may change and
it may only increase. Similarly, a decrease of $P^{*}$ may only decrease the
left hand side. However, the algorithm does increase the last column of
$P^{*}$ whenever an decrease of $P^{*}$ occurs. Note however, that the last
coordinate of $x^{*}$ is is always $0$ as coordinate $n+1$ is never boosted
(due to the last column of $C*$ being $0$ $\lambda(x^{*},n+1)$ is unbounded
hence coordinate $n+1$ is never cheap).

It remains to argue that during Boost calls the inequality is maintained.
Assume coordinate $i$ is boosted by $\delta$ and at the start of the boosting
process the inequality holds. Define
$f_{p}(x^{*})=\eta\cdot\log(\sum_{i\in[m_{p}]}\exp(\eta P^{*}_{i}x^{*}))$ and
$f_{c}(x^{*})=-\eta\cdot\log(\sum_{i\in[m_{c}]}\exp(-\eta C^{*}_{i}x^{*}))$
analogously to Section LABEL:sec:lowerbound. Following the proof of Property
3.4 we get that $f_{p}(x^{*}+\delta\cdot
e_{i})-f_{p}(x^{*})\leq(f_{c}(x^{*}+\delta\cdot
e_{i})-f_{c}(x^{*}))\cdot(1+50\cdot\epsilon)$ (note that a different constant
$50\epsilon$ appears as the amount of slack the algorithm uses is different).
As both function are monotonous in $x^{*}$ and relaxing updates may only
increase $f_{c}(x^{*})$ and reduce $f_{p}(x^{*})$ we have that at all times
$f_{c}(x^{*})\cdot(1+50\cdot\epsilon)\geq f_{p}(x^{*})$.

By the properties of $f_{c}(x^{*})$ and $f_{p}(x^{*})$ (stated in Section 3.1
as Equation 3.2 we can conclude that
$\max_{i\in[m_{p}]}\\{P^{*}_{i}x^{*}\\}\leq\min_{i\in[m_{c}]}\\{C^{*}_{i}x^{*}\\}\cdot(1+50\cdot\epsilon)+\epsilon\cdot(1+50\cdot\epsilon))\leq\min_{i\in[m_{c}]}\\{C^{*}_{i}x^{*}\\}\cdot(1+50\cdot\epsilon)+100\cdot\epsilon$
at all times.

Let $\delta$ stand for the value of the last boost. By definition
$C^{*}\delta\leq\mathbb{1}\cdot\epsilon$ hence at all times
$\min_{j\in[m_{c}]}\\{C^{*}_{j}x^{*}\\}\leq 1+\epsilon$. Therefore at all
times
$\max_{i\in[m_{p}]}\\{P^{*}_{i}x^{*}\\}\leq(1+50\epsilon)\cdot(1+\epsilon)+100\epsilon\leq
1+200\epsilon$ that is $P^{*}x^{*}\leq\mathbb{1}\cdot(1+200\epsilon)$.

∎

######  Corollary C.5.

If $\epsilon\leq 1/200$ then at all times $w_{p}(x^{*})\leq\exp(3\cdot\eta)$
and $w_{x}(x^{*})\geq\exp(2\cdot\eta)$, hence
$\lambda_{0}(x^{*})\leq\exp(5\cdot\eta)$.

###### Proof.

$w_{p}(x^{*})\leq
m_{p}\cdot\exp(\eta\cdot\max_{i\in[m_{p}]}\\{P^{*}_{i}x^{*}\\})\leq\exp(\eta(2+200\cdot\epsilon))\leq\exp(\eta\cdot
3)$. As argued in the proof of Claim C.3 we have that
$\min_{j\in[m_{c}]}\\{C^{*}_{j}x^{*}\\}\leq 1+\epsilon$ at all times, hence
$w_{c}(x^{*})\geq\exp(-\eta\cdot\min_{j\in[m_{c}]}\\{C^{*}_{j}x^{*}\\})\geq\exp(-2\cdot\eta)$..

∎

######  Lemma C.6.

Whenever the algorithm halts without returning an answer the extended linear
program is infeasible. If the algorithm may only return an $O(\epsilon)$
approximate solution to the extended linear program.

###### Proof.

The lemma follows from Claim C.2 and Claim C.1

∎

###  C.4 Running Time

######  Claim C.4.

For any $k\in[n]$ Boost(k) may be called at most
$O(\frac{\log^{2}(m+U/L)}{\epsilon^{2}})=O(\frac{\log(m+U/L)\cdot\eta}{\epsilon})$
number of times.

###### Proof.

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

Consider any call to the Boost$(x^{*})$ 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 Algorithm 2,
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\leq\epsilon/\eta$, or there exists a not-too-large
covering constraint $j\in[m_{c}]$181818We say that a covering constraint
$j\in[m_{c}]$ is not-too-large iff $C^{*}_{j}x^{*}<2$. with
$C(j,k)\cdot\delta\leq\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$(k)$.191919Note 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$(k)$.

Due to Assumption C.2 we can assume that $U=2^{\tau}\cdot L$ for some integer
$\tau=O(\log n)$. 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 C.5.

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

###### 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$(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$(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 the definition of Algorithm 2, it
follows that this call increases $x_{k}$ by $\delta=\epsilon/(\eta\alpha\cdot
4)\geq\epsilon/(\eta L2^{\ell+2})$.

Suppose that $T$ covering-critical calls have been made to the Boost$(x,k)$
subroutine, where $T>16\cdot\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+2})$.

Since $x_{k}=0$ initially and it increases monotonically over time, just
before the last critical call $\Gamma_{T}$ we have
$x_{k}\geq(T-1)\cdot\epsilon/(\eta
L2^{\ell+2})\geq(16\eta/\epsilon)\cdot\epsilon/(\eta
L2^{\ell+2})=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}$. This leads to
a contradiction. Hence, we must have $T\leq 16\cdot\eta/\epsilon$, and this
concludes the proof of the claim.

∎

######  Claim C.6.

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

###### Proof.

(Sketch) As in the proof of Claim C.5, 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$(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$(k)$
subroutine, where $T>16\cdot\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 C.5, we conclude that $P_{i_{T}}\cdot x>2$
just before the call $\Gamma_{T}$. By Claim C.3 this leads to a contradiction
(assuming $\epsilon<1/200$). Thus, it must be the case that $T\leq
16\eta/\epsilon$, and this concludes the proof of the claim.

∎

Any call to the subroutine Boost$(k)$ has pivot in $[m_{p}]\cup[m_{c}]$ and
pivot-value in $\mathcal{I}_{\ell}$ for some
$\ell\in\\{0,\ldots,\tau-1\\}$.202020This 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}$.  Accordingly, from Claim 3.1
and Claim 3.2, it follows that the total number of calls made to the
Boost$(k)$ during the course of our dynamic algorithm is at most
$2\cdot\tau\cdot(16\eta/\epsilon)=O(\frac{\log^{2}(m+U/L)}{\epsilon^{2}})$.

∎

######  Claim C.7.

All calls to UpdatePWeights and UpdateCWeights be handled in
$O(\frac{\log^{2}(m+U/L)\cdot N}{\epsilon^{2}})$ total time.

###### Proof.

As each call to Boost calls the weight update functions once by Claim C.4 they
will be called a total of $O(\frac{\log(m+U/L)\cdot\eta}{\epsilon}\cdot n)$
times. Fix $k\in[n]$. UpdatePWeights($k$) and UpdateCWeights($k$) will be
called $O(\frac{\log(m+U/L)\cdot\eta}{\epsilon})$ times. Hence, the outer
loops of both function will take
$O(N\cdot\frac{\log(m+U/L)\cdot\eta}{\epsilon})$ total time to handle.

Without loss of generality focus on UpdatePWeights. For any $i\in[m_{p}]$
between any two updates to $\hat{w}_{p}(x^{*},i)$ $w_{p}(x^{*},i)$ must
increase by a factor of $1+\Omega(\epsilon)$. Due to Corollary C.5 this may
happen at most $O(\log^{2}(m+U/L)/\epsilon^{2})$ times. After updating
$\hat{w}_{p}(x^{*},i)$ the algorithm will spend $O(R^{P}_{i})$ time updating
$\hat{\lambda}_{0}(x^{*})(x^{*},k)$ values. Therefore, over all $i\in[m_{p}]$
the total work to maintain $\hat{\lambda}_{0}(x^{*})(x^{*},k)$ values will be
in $O(\frac{\log^{2}(m+U/L)}{\epsilon^{2}})$. The proof proceeds similarly for
the work UpdateCWeights does on maintaining
$\hat{\lambda}_{0}(x^{*})(x^{*},k)$ values.

∎

######  Claim C.8.

The total time spent by the algorithm through calls to the Boost subroutine is
in $O(\frac{\log^{2}(m+U/L)\cdot N}{\epsilon^{2}})$

###### Proof.

Each call to Boost($k$) requires 3 non-constant time tasks. Firstly an
estimate of $\delta_{k}$ has to be sampled. By Claim C.11 and Claim C.4 these
samplings will take $O(N\cdot\frac{\log(m+U/L)}{\epsilon^{2}})$ total time.

Afterwards the algorithm updates all $w_{p}(x^{*},i)$ for
$i\in[m_{p}]|P^{*}(i,k)>0$ and $w_{c}(x^{*},j)$ for $j\in[m_{c}]|C^{*}(j,k)>0$
in $O(N^{P}_{k}+N^{C}_{k})$ time. Over all calls to boost this will take total
$O(N\cdot\frac{\log^{2}(m+U/L)}{\epsilon^{2}})$ time by Claim C.11.

Finally, the algorithm makes calls to UpdatePWeights($k$) and
UpdateCWeights($k$) (see Algorithms 4 and 3). This will take total time
$O(N\cdot\frac{\log^{2}(m+U/L)\cdot N}{\epsilon^{2}})$ by Claim C.7.

∎

######  Claim C.9.

The total time by the UpdateP and UpdateC subroutines (outside of calls to
Iterate and Boost) is bounded by $O(\frac{\log^{2}(m+U/L)\cdot
N}{\epsilon^{2}}+t)$.

###### Proof.

The only action UpdateP does which is not in $O(1)$ is the while loop. Due to
Claim C.4 the while loops will test a coordinates price at most
$O(n\cdot\frac{\log^{2}(m+U/L}{\epsilon^{2}}+t)$ time over the total run of
the algorithm.

Similarly, the while loops of UpdateC may also only have
$O(n\cdot\frac{\log^{2}(m+U/L}{\epsilon^{2}}+t)$ iterations due to Claim C.4.
The only other non-constant time operation of UpdateC is the process of
updating $\hat{w}_{c}(x^{*},j)$ and affected $\hat{\lambda}(x^{*},k^{\prime})$
values. Whenever $\hat{w}_{c}(x^{*},j)$ is updated $R^{C}_{j}$ values of
$\hat{\lambda}(x^{*},k^{\prime})$ will be updated. As an update to
$\hat{w}_{c}(x^{*},j)$ increases its value by a multiplicative factor of at
least $1+\epsilon$ due to Assumption C.2 there can be at most
$O(\log(N)/\epsilon)$ updates of $\hat{w}_{c}(x^{*},j)$. Therefore, the
maintenance of the slack parameters will take at most
$O(\frac{N\cdot\log(N)}{\epsilon}+t)$ total time for UpdateC. This finishes
the proof.

∎

######  Lemma C.7.

Algorithm 1 runs in $O(\frac{N\cdot\log^{2}(m+U/L)}{\epsilon^{2}}+t)$
deterministic time.

###### Proof.

The time spent by calls to Boost or updates is handled in
$O(\frac{N\cdot\log^{2}(m+U/L)}{\epsilon^{2}}+t)$ total time by Claim C.8 and
Claim C.9. Between each call to iterate $\lambda_{0}(x^{*})$ increases by a
factor of $1/(1-\epsilon)$. As $\lambda_{0}(x^{*})\leq\exp(5\cdot\eta)$ by
Corollary C.5 there will be at most
$O(\eta/\epsilon)=O(\log(m+U/L)/\epsilon^{2})$ calls to Iterate() which will
take $O(\frac{N\cdot\log^{2}(m+U/L)}{\epsilon^{2}})$ to complete (apart from
Boost calls). This completes the lemma.

∎

###  C.5 Maintenance of an estimate of $\delta_{k}$ for Algorithm 2

To imitate the increments of the static algorithm described by Figure 9 when
Boost($k$) is called we would like to find
$\delta=\max_{\delta}\\{\max\\{\max_{i}P^{*}(i,k)\cdot\delta,\max_{j|C^{*}_{j}x^{*}<2}C^{*}(j,k)\cdot\delta\\}=\epsilon/\eta$.
Unfortunately, under dynamic relaxing updates returning the exact $\delta_{k}$
is too slow. Therefore, we will implement an efficient oracle which returns
$\delta\in[\delta_{k}\cdot(1-\epsilon),\delta_{k}]$ when queried in $O(1)$
time.

##### Max-Heap:

Using folklore data structures we will assume that a max-heap on at most
$m=m_{c}+m_{p}$ objects is a black-box tool which can handle the following
actions:

  * •

In $O(1)$ the max-heap returns the maximum-element stored in the heap

  * •

In $O(\log(m))$ time an element can be removed from the heap

  * •

In $O(\log(m))$ time an element can be added to the heap

##### Initialization:

At initialization the oracle implements $n$ max heaps $H_{k}:k\in[n]$, one for
each coordinate of $x^{*}$. We will now describe the implementation of a
specific heap $H_{k}$. $H_{k}$ will consist of at most $N^{C}_{k}+N^{P}_{k}$
objects each representing a non-zero element of the $k$-th column of $C^{*}$
or $P^{*}$. Each non-zero element of these two columns will be inserted into
the heap with it’s initial value and an identifier. Hence, the top element of
$H_{k}$ will represent the largest value in the $k$-th column of $C^{*}$ and
$P^{*}$.

##### Update to $P^{*}$:

Assume that due to a relaxing update $P^{*}(i,k)$ reduced by $\Delta$ to some
$P_{+}^{*}(i,k)$. The oracle will look-up the value $P^{*}(i,k)$ currently
represented under in $H_{k}$, say this value is $P_{-}^{*}(i,k)$. If
$P_{-}^{*}(i,k)>2\cdot P_{+}^{*}(i,k)$ then the oracle will remove
$P_{-}^{*}(i,k)$ from $H_{k}$ and re-enter it as $P_{+}^{*}(i,k)$. If
$P_{-}^{*}(i,k)\leq 2\cdot P_{+}^{*}(i,k)$ then the oracle doesn’t change
anything in the heap $H_{k}$.

##### Update to $C^{*}$:

Assume that due to a relaxing update $C^{*}(j,k)$ increased by $\Delta$ to
some $C_{+}^{*}(j,k)$. If previously to the update $(C^{*})_{i}x^{*}<2$
however after the update $(C^{+}_{*})_{i}x^{*}\geq 2$ the oracle proceeds over
all non-zero entries of the $j$-th row of $C^{*}$ (iterate over all
$k^{\prime}\in[m_{c}]|C^{*}(j,k^{\prime})>0$) of the form
$C^{*}(j,k^{\prime})>0$ and removes them from their corresponding heaps.
Otherwise the oracle proceeds similarly to its behaviour under a packing
update: say that the value of $C^{*}(j,k)$ stored in $H_{k}$ is
$C^{*}_{-}(j,k)$. If $C^{*}_{-}(j,k)<2\cdot C^{*}_{+}(j,k)$ then the oracle
removes the $C^{*}_{-}(j,k)$ node from the heap and re-enters it as the
current value $C^{*}_{+}(j,k)$. If $C^{*}_{-}(j,k)\geq 2\cdot C^{*}_{+}(j,k)$
the oracle rests.

##### Query of $\delta_{k}$

: Let the top element of heap $H_{k}$ when the query is made be $\kappa$. The
oracle will return value $\delta=\frac{\eta}{\epsilon\cdot\kappa/2}$.
Afterwards, the oracle proceeds to adjust it’s max-heaps to the boost of
coordinate $k$. Let $x^{*}_{+}$ and $x^{*}_{-}$ represent the state of $x^{*}$
after and before having been incremented by $\delta\cdot e_{k}$ through
Boost($k$) respectively. The oracle iterates through all $j\in[m_{c}]$ such
that $C^{*}(j,k)>0$. For any such $j$ if $(C^{*}_{-})_{j}x^{*}<2$ however
$(C^{*}_{+})_{j}x^{*}>2$ the oracle proceeds as follows: for all
$k^{\prime}\in[n]|C^{*}(j,k^{\prime})>0$ the oracle removes
$C^{*}(j,k^{\prime})$ (or the value stored as the representative of
$C^{*}(j,k^{\prime})$ which might be somewhat smaller) from heap
$H_{k^{\prime}}$.

######  Claim C.10.

If the oracle is queried to return an estimate of $\delta_{k}$ it returns a
value in $[\delta_{k}/4,\delta_{k}]$

###### Proof.

Assume Boost($k$) was called and the oracle is queried to return an estimate
of $\delta_{k}$. Observe, that at all time points the heap $H_{k}$ contains an
object corresponding to each non-zero elements of the $k$-th column of
$P^{*}$. Furthermore, $H_{k}$ contains an element for each
$C^{*}(j,k):j\in[m_{c}]|C^{*}_{j}<2$. Fix an element of $P^{*}$ represented in
$H_{k}$, say $P^{*}(i,k)$ and let $P^{*}_{-}(i,k)$ stand for the value it is
represented under in the heap $H_{k}$. Observe that by construction
$P^{*}_{-}(i,k)\leq P^{*}(i,k)\leq P^{*}_{-}(i,k)$. Fix an element of $C^{*}$
represented in $H_{k}$, say $C^{*}(j,k)$ and let it’s representation in
$H_{k}$ have value $C^{*}_{-}(j,k)$. Similarly, observe by construction that
$C^{*}_{-}(j,k)\cdot 2\geq C^{*}(j,k)\geq C^{*}_{-}(j,k)$.

Define
$\kappa=\max\\{\max_{i\in[m_{p}]}P^{*}(i,k),\max_{j\in[m_{c}]|C^{*}_{j}x^{*}<2}C^{*}(j,k)\\}$.
By the observations above we can conclude that the maximum element of $H_{k}$
is in $[\kappa/2,\kappa\cdot 2]$. Therefore, the oracle returns a value in
$[\frac{\epsilon}{4\cdot\kappa\cdot\eta},\frac{\epsilon}{\kappa\cdot\eta}]=[\delta_{k}/4,\delta_{k}]$.

∎

######  Claim C.11.

Let $B_{k}:k\in[n]$ represent the number of times Algorithm 1 calls subroutine
Boost($k$). The total time it takes to maintain the oracle and return it’s
queries is in $O(\sum_{k\in[n]}B_{k}N^{C}_{k}+N\cdot\log^{2}(N)+t)$.

###### Proof.

Say that the oracle re-adjust a constraint parameter $P^{*}(j,k)$ or
$C^{*}(i,k)$ whenever it removes their outdated value for heap $H_{k}$ and
inserts their current value in the constraint matrix. Whenever a replacement
of a constraint parameter occurs it’s value in $H_{k}$ has to double if it’s a
member of $C^{*}$ or halve if its a member of $P^{*}$ respectively. By
Assumption C.2 non-zero parameters of constraint matrices always lie in
$[1/poly(N),poly(N)]$ therefore each constraint element may has its value re-
adjusted at most $O(\log(N))$ times. This means that handling re-adjustments
of all elements of the heaps maintained by the oracle can be completed in
$O(N\cdot\log^{2}(N))$ total time.

When an update is made to $P^{*}$ the oracle checks the value of a single
element in the heap, therefore it’s work outside of possibly re-adjusting said
value can be completed in $O(1)$ time. This means $O(N\cdot\log^{2}(N)+t)$
upper bounds the work of the oracle handling packing constraint updates.

When an update is made to $C^{*}$, say to $C^{*}(j,k)$, the oracle first has
to check weather $C^{*}_{j}x^{*}$ has exceeded $2$ for the first time.
Checking the value of $C^{*}_{j}x^{*}$ can be completed in $O(1)$ time
(assuming the algorithm keeps track of each constraints progress at all
times). The value of $C^{*}(j,k)$ may only exceed $2$ once over the total run
of the iteration. At this point the oracle removes $R^{C}_{j}$ elements from
it’s heaps. All of these removals therefore will take at most
$O(N\cdot\log(N))$ total time. Therefore, $O(N\cdot\log^{2}(N)+t)$ upper
bounds the work of the oracle handling covering constraint updates.

When a coordinate $k$ is boosted by Algorithm 2 the oracle has to iterate over
all non-zero elements of the $k$-th column of $C^{*}$ which takes
$O(N^{C}_{k})$ time. For all $j\in[m_{c}]|C^{*}(j,k)>0$ the oracle calculates
$C^{*}_{j}x^{*}$ in $O(1)$. Afterwards, the oracle may proceed to remove all
elements in any such line of $C^{*}$, however each element may only be removed
at most once. Therefore, all work of the oracle due to boosting queries can be
upper bounded by $O(\sum_{k\in[n]}B_{k}N^{C}_{k}+N\cdot\log(N)+t)$. This
finishes the proof.

∎

###  C.6 The Handling of Translation Updates

Using Theorem C.1 as a black-box statement we will show how the algorithm can
handle translation updates in addition to element-wise updates without
incurring any blow-up in the total running time. To re-iterate a mixed packing
covering linear program defined by constraint matrices $(P,C)$ is the problem
of finding $x$ such that $Px\leq\mathbb{1},Cx\geq\mathbb{1}$. A relaxing
translation update of the packing constraint could formalized as follows: for
some coordinate $i:i\in[m_{p}]$ and $\gamma>0$ we update the linear program
such that we are looking for $x$ satisfying $Px\leq\mathbb{1}+\gamma\cdot
e_{i},Cx\geq\mathbb{1}$. Similarly, a relaxing translation update to the
covering matrix is an updated defined by some $j\in[m_{c}]$ and $\gamma>0$
such that we update the linear program to
$Px\leq\mathbb{1},Cx\geq\mathbb{1}-\gamma\cdot e_{j}$.

######  Observation C.8.

Let $\Delta_{P}\in\Re_{\geq 0}^{m_{p}}$ and $\Delta_{C}\in\Re_{\geq
0}^{m_{c}}$ where $0\leq\Delta_{P}\leq\mathbb{1}\cdot\epsilon$ and
$0\leq\Delta_{C}\leq\mathbb{1}\cdot\epsilon$. If $x$ is an
$\epsilon$-approximate solution to the linear program defined by constraint
matrices $(P,C)$ then $x$ is a $2\cdot\epsilon$ approximate solution to the
linear program defined by $(P+\Delta_{P},C-\Delta_{C})$.

As demonstrated by Observation C.8 if the algorithm ignores translation
updates until any constraint is translated by more than an $\epsilon$ factor
the solution returned is still $O(\epsilon)$ approximate to the linear
program. Once a constraint (say the $i$-th pacing constraint) is translated by
at least an $\epsilon$ factor the algorithm can simulate this relaxation
through $R^{P}_{i}$ entry updates of the packing matrix by relaxing all
elements in the $i$-th row of $P$ by the same multiplicative factor. Assuming
similarly as in Assumption C.2 that all input parameters lie in the
$[1/poly(N),poly(N)]$ range we can be certain that each constraint will need
to be updated at most
$O(\log_{1+\epsilon}(poly(N))=O(\frac{\log(N)}{\epsilon})$ times due to being
translated by more than an $\epsilon$ factor. Hence, the total number of
entry-wise updates required to handle all translation updates will be bounded
by $O(N\cdot\frac{\log(N)}{\epsilon})$.

Therefore, the algorithm can handle translation updates with
$O(N\cdot\frac{\log(N)}{\epsilon}+t)$ additional time (where $t$ here stands
for the number of translation updates) as the algorithm of Theorem C.1 runs in
linear time with respect to the number of entry wise updates. This implies
that Theorem C.1 can be extended to work for translation updates without
incurring any loss in running time.

## References

  * [ABD22] Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja.  Decremental matching in general graphs.  In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [ABFP13] Yossi Azar, Umang Bhaskar, Lisa Fleischer, and Debmalya Panigrahi.  Online mixed packing and covering.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 85–100. SIAM, 2013.
  * [ABL20] Sepehr Assadi, Aaron Bernstein, and Zachary Langley.  Improved bounds for distributed load balancing.  arXiv preprint arXiv:2008.04148, 2020.
  * [ACC+18] Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc.  Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms.  In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 7:1–7:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [AEM92] Pankaj K. Agarwal, David Eppstein, and Jirí Matousek.  Dynamic half-space reporting, geometric optimization, and minimum spanning trees.  In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 80–89. IEEE Computer Society, 1992.
  * [AG11] Kook Jin Ahn and Sudipto Guha.  Linear programming in the semi-streaming model with application to the maximum matching problem.  In International Colloquium on Automata, Languages, and Programming, pages 526–538. Springer, 2011.
  * [AG18] Kook Jin Ahn and Sudipto Guha.  Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints.  ACM Transactions on Parallel Computing, 4(4):17:1–17:40, 2018\.
  * [AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory Comput., 8(1):121–164, 2012.
  * [AJJ+22] Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian.  Semi-streaming bipartite matching in fewer passes and optimal space.  In Proceedings of the Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627–669. SIAM, 2022.
  * [AP14] Pankaj K Agarwal and Jiangwei Pan.  Near-linear algorithms for geometric hitting sets and set covers.  In Proceedings of the thirtieth annual symposium on Computational geometry, pages 271–279, 2014.
  * [ARW17] Amir Abboud, Aviad Rubinstein, and R. Ryan Williams.  Distributed PCP theorems for hardness of approximation in P.  In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 25–36, 2017.
  * [AZO19] Zeyuan Allen-Zhu and Lorenzo Orecchia.  Nearly linear-time packing and covering lp solvers.  Mathematical Programming, 175(1):307–353, 2019.
  * [BBCG22] Suman K Bera, Sayan Bhattacharya, Jayesh Choudhari, and Prantar Ghosh.  A new dynamic algorithm for densest subhypergraphs.  In Proceedings of the ACM Web Conference 2022, pages 1093–1103, 2022.
  * [BBR04] Yair Bartal, John W Byers, and Danny Raz.  Fast, distributed approximation algorithms for positive linear programming with applications to flow control.  SIAM Journal on Computing, 33(6):1261–1279, 2004.
  * [BG95] Hervé Brönnimann and Michael T Goodrich.  Almost optimal set covers in finite vc-dimension.  Discrete & Computational Geometry, 14(4):463–479, 1995.
  * [BGS20] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak.  Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1123–1134. IEEE, 2020.
  * [BHN19] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  A new deterministic algorithm for dynamic set cover.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 406–423, 2019.
  * [BHR18] Aaron Bernstein, Jacob Holm, and Eva Rotenberg.  Online bipartite matching with amortized replacements.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 947–959. SIAM, 2018.
  * [BK21] Sayan Bhattacharya and Peter Kiss.  Deterministic rounding of dynamic fractional matchings.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 27:1–27:14, 2021.
  * [BN09a] Niv Buchbinder and Joseph Naor.  Online primal-dual algorithms for covering and packing.  Mathematics of Operations Research, 34(2):270–286, 2009.
  * [BN+09b] Niv Buchbinder, Joseph Seffi Naor, et al.  The design of competitive online algorithms via a primal–dual approach.  Foundations and Trends® in Theoretical Computer Science, 3(2–3):93–263, 2009.
  * [Bsh16] Nader H Bshouty.  Derandomizing chernoff bound with union bound with an application to $k$-wise independent sets.  arXiv preprint arXiv:1608.01568, 2016.
  * [CH20] Timothy M Chan and Qizheng He.  Faster approximation algorithms for geometric set cover.  arXiv preprint arXiv:2003.13420, 2020.
  * [Cla93] Kenneth L Clarkson.  Algorithms for polytope covering and approximation.  In Workshop on Algorithms and Data Structures, pages 246–252. Springer, 1993.
  * [CQ18] Chandra Chekuri and Kent Quanrud.  Randomized mwu for positive lps.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 358–377. SIAM, 2018.
  * [Epp91] David Eppstein.  Dynamic three-dimensional linear programming.  In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 488–494. IEEE Computer Society, 1991.
  * [Fle00] Lisa K Fleischer.  Approximating fractional multicommodity flow independent of the number of commodities.  SIAM Journal on Discrete Mathematics, 13(4):505–520, 2000.
  * [FS97] Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139, 1997.
  * [FS99] Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  Games and Economic Behavior, 29(1-2):79–103, 1999.
  * [GGK13] Albert Gu, Anupam Gupta, and Amit Kumar.  The power of deferral: maintaining a constant-competitive steiner tree online.  In ACM Symposium on Theory of Computing Conference (STOC), pages 525–534. ACM, 2013.
  * [GK02] Naveen Garg and Rohit Khandekar.  Fast approximation algorithms for fractional steiner forest and related problems.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 500–509. IEEE, 2002.
  * [GK07] Naveen Garg and Jochen Könemann.  Faster and simpler algorithms for multicommodity flow and other fractional packing problems.  SIAM Journal on Computing, 37(2):630–652, 2007.
  * [GK14] Anupam Gupta and Amit Kumar.  Online steiner tree with deletions.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 455–467. SIAM, 2014.
  * [GKKP17] Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi.  Online and dynamic algorithms for set cover.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 537–550. ACM, 2017.
  * [GKL21] Anupam Gupta, Gregory Kehne, and Roie Levin.  Random order set cover is as easy as offline.  arXiv preprint arXiv:2111.06842, 2021.
  * [GKS14] Anupam Gupta, Amit Kumar, and Cliff Stein.  Maintaining assignments online: Matching, scheduling, and flows.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 468–479. SIAM, 2014.
  * [GN12] Anupam Gupta and Viswanath Nagarajan.  Approximating sparse covering integer programs online.  In International Colloquium on Automata, Languages, and Programming, pages 436–448. Springer, 2012.
  * [GP13] Manoj Gupta and Richard Peng.  Fully dynamic (1+ e)-approximate matchings.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 548–557. IEEE, 2013.
  * [HIPS19] Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis, and David Saulpic.  Dominating sets and connected dominating sets in dynamic graphs.  In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 35:1–35:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [HLLT06] Nicholas JA Harvey, Richard E Ladner, László Lovász, and Tami Tamir.  Semi-matchings for bipartite graphs and load balancing.  Journal of Algorithms, 59(1):53–78, 2006.
  * [HWC17] Shuguang Hu, Xiaowei Wu, and TH Hubert Chan.  Maintaining densest subsets efficiently in evolving hypergraphs.  In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 929–938, 2017.
  * [IMR+17] Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee.  Fractional set cover in the streaming model.  In 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problem (APPROX 2017), 2017.
  * [IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  Journal of Computer and System Sciences, 63(4):512–530, 2001.
  * [JJST22] Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian.  Regularized box-simplex games and dynamic decremental bipartite matching.  In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 77:1–77:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [KY14] Christos Koufogiannakis and Neal E. Young.  A nearly linear-time PTAS for explicit fractional packing and covering linear programs.  Algorithmica, 70(4):648–674, 2014.
  * [Lit88] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  Machine learning, 2(4):285–318, 1988.
  * [LN93] Michael Luby and Noam Nisan.  A parallel approximation algorithm for positive linear programming.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 448–457, 1993.
  * [Mat93] Jirí Matousek.  Linear optimization queries.  J. Algorithms, 14(3):432–448, 1993.
  * [OvL80] Mark H. Overmars and Jan van Leeuwen.  Dynamically maintaining configurations in the plane (detailed abstract).  In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 135–145. ACM, 1980.
  * [OvL81] Mark H. Overmars and Jan van Leeuwen.  Maintenance of configurations in the plane.  J. Comput. Syst. Sci., 23(2):166–204, 1981.
  * [PST95] Serge A Plotkin, David B Shmoys, and Éva Tardos.  Fast approximation algorithms for fractional packing and covering problems.  Mathematics of Operations Research, 20(2):257–301, 1995.
  * [Qua20] Kent Quanrud.  Nearly linear time approximations for mixed packing and covering problems without data structures or randomization.  In 3rd Symposium on Simplicity in Algorithms (SOSA), pages 69–80, 2020.
  * [Tre98] Luca Trevisan.  Parallel approximation algorithms by positive linear programming.  Algorithmica, 21(1):72–88, 1998.
  * [Waj20] David Wajc.  Rounding dynamic matchings against an adaptive adversary.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 194–207. ACM, 2020.
  * [WRM15] Di Wang, Satish Rao, and Michael W Mahoney.  Unified acceleration method for packing and covering problems via diameter reduction.  arXiv preprint arXiv:1508.02439, 2015.
  * [You14] Neal E Young.  Nearly linear-work algorithms for mixed packing/covering and facility-location linear programs.  arXiv preprint arXiv:1407.3015, 2014.
  * [ZN01] Edo Zurel and Noam Nisan.  An efficient approximate allocation algorithm for combinatorial auctions.  In Proceedings of the 3rd ACM conference on Electronic Commerce, pages 125–136, 2001.
  * [ZO15] Zeyuan Allen Zhu and Lorenzo Orecchia.  Nearly-linear time positive LP solver with faster convergence rate.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), pages 229–236. ACM, 2015.