Theorem 1.1 .

There is an algorithm which solves incremental max flow whp in amortized $n^{o(1)}\varepsilon^{-3}$ time per update, against adaptive adversaries.

•

Input: Vertex set $V$ , two vertices $s,t\in V$ , parameter $\varepsilon>0$ .
•

Updates: A sequence of $m\leq\operatorname{poly}(n)$ edge insertions, each with a capacity $u_{e}\in[1,U]$ .
•

Output: Maintain a $(1+\varepsilon)$ -apx maximum flow through the updates.

Theorem 2.1 .

There is a randomized algorithm for incremental thresholded $\ell_{p}$ -norm flow problem, when given an initial flow $f^{(0)}$ and inputs bounded by $\widetilde{O}(1)$ in fixed-point arithmetic (what is this?), runs in time $p^{2}m^{1+o(1)}\log(\mathcal{E}(f^{(0)})-F/\varepsilon)$ .

•

Input: An $\ell_{p}$ -norm flow instance with $(G,w^{G},d)$ , threshold $F$ , parameter $\varepsilon$ .
•

Updates: Edge insertions (with corresponding $w^{G}$ )
•

Output: Either certify correctly that $OPT>F$ , or return a feasible flow $f$ with $\mathcal{E}(f)\leq F+\varepsilon$ .

where the $\ell_{p}$ -norm flow problem is

•

Input: Undirected graph $G$ , edge weights $w^{G}\geq 0$ , demand vector $d\in\mathbb{R}^{V}$ .
•

Output: minimize $\mathcal{E}(f)=\left\lVert W^{G}f\right\rVert_{p}^{p}$ over all flows $B^{\mkern-1.5mu\mathsf{T}}f=d$ .

Lemma 2.2 .

For any $f$ and $x$ , energy drops by at least the residual when adding circulation $x$

\mathcal{E}(f+x)-\mathcal{E}(f)\leq\mathcal{R}_{f}(x)

and there is some amount of the circulation that can be added, where the energy doesn’t drop by too much

\mathcal{E}(f+\lambda x)-\mathcal{E}(f)\geq\lambda\mathcal{R}_{f}(x)

for some $\lambda=O(p)$ .

Lemma 2.3 .

Certificate : Fix any threshold $F>0$ . If there exists a flow $f$ such that for all circulations $c$ , $\mathcal{R}_{f}(c)>(F-\mathcal{E}(f))/\lambda$ , then the $p$ -norm flow instance satisfies $OPT>F$ .

Lemma 2.4 .

Improvement : For any flow $f$ and any circulation $c$ such that $\mathcal{R}_{f}(c)\leq-\beta\cdot\hat{R}$ ,

\mathcal{E}(f+c)-F\leq\left(1-\frac{\beta}{\lambda}\right)\cdot\left(\mathcal{% E}(f)-F\right)

Theorem 3.1 .

There is an algorithm for solving the $\beta$ -apx residual problem.

•

Input: an $\ell_{p}$ -norm flow instance $(G,w^{G},d)$ , a feasible flow $f$ for this instance, a threshold $F>0$ .

•

Definition: the residual threshold is $\hat{R}=\frac{\mathcal{E}(f)-F}{\lambda}$ , and the residual problem $\mathcal{R}_{f}(x)$ is

\mathcal{R}_{f}(x)=\left\langle g,x\right\rangle+\|Rx\|_{2}^{2}+\|Wx\|_{p}^{p}

•
Output: either
- –
  
  Certificate : for all circulations $c$ , $\mathcal{R}_{f}(c)\geq-\hat{R}$ .
- –
  
  Improvement : return a circulation $c$ such that $\mathcal{R}_{f}(c)\leq-\beta\cdot\hat{R}$

where $g=p(W^{G})^{p}|f|^{p-2}f,r=\sqrt{2p^{2}(W^{G})^{p}|f|^{p-2}},w=pw^{G}$ .

Lemma 3.2 .

Certificate : Fix any $\hat{R}>0$ and $g, r, w$ as in the residual problem. If no circulation $c$ satisfies

\langle g,c\rangle=-1,\qquad\|2\sqrt{\hat{R}}Rc\|_{2}\leq 1,\qquad\|\hat{R}^{(% p-1)/p}Wc\|_{p}\leq 1,

then every circulation must have $\mathcal{R}(c)>-\hat{R}$ .

Lemma 3.3 .

Improvement : Given any $\hat{R}>0$ and an incremental $K$ -apx residual solution for $g, r, w$ , if there is a circulation $c$ with

\langle g,c\rangle=-1,\qquad\|2\sqrt{\hat{R}}Rc\|_{2}\leq K,\qquad\|\hat{R}^{(% p-1)/p}Wc\|_{p}\leq K

then for the circulation $c^{\prime}=\frac{\hat{R}}{2K^{2}}c$ ,

\mathcal{R}(c^{\prime})\leq-\frac{\hat{R}}{6K^{2}}

Theorem 4.1 .

There is a randomized algorithm for the incremental $K$ -apx residual problem that runs in $m^{1+o(1)}$ time and succeeds with high probability against an adaptive adversary.

•

Input: Incremental graph $G$ with $(g,r,w)$ weights and a parameter $K\geq 1$ .
•
Output: Either
1. 1.
  
  certify that there is no circulation $c^{*}$ such that $\langle g,c^{*}\rangle=-1,\|Rc\|_{2}\leq 1$ and $\|Wc\|_{p}\leq 1$ , or
2. 2.
  
  output a circulation $c$ such that $\langle g,c^{*}\rangle=-1,\|Rc\|_{2}\leq K$ and $\|Wc\|_{p}\leq K$ .

Lemma 4.2 .

Initially, $\Phi^{(0)}=K^{2}$ and $\Psi^{(0)}=K^{q}$ .

Lemma 4.3 .

At any iteration $i$ , $\Phi^{(i+1)}\leq\Phi^{(i)}+\frac{3K^{2}}{T}$ .

Lemma 4.4 .

At any iteration $i$ , $\Psi^{(i+1)}\leq\Psi^{(i)}+\frac{4qK^{q}}{T}$ .

Lemma 4.5 .

Improvement : When Algorithm 2 returns $c^{(T)}$ , we have

\Phi^{(T)}\leq 4K^{2}\qquad\text{and}\qquad\Psi^{(T)}\leq 5qK^{q}

Therefore, we have

\|Rc^{(T)}\|_{2}\leq 2K\qquad\text{and}\qquad\|Wc^{(T)}\|_{p}\leq 2K

Lemma 4.6 .

Certificate : At any iteration $i$ , if there is no circulation $c$ that satisfies

\langle g,c\rangle=-1,\qquad\|L^{(i)}c\|_{1}\leq 20qK^{q-1}

then there is no circulation $c$ such that $\langle g,c\rangle=-1,\|Rc\|_{2}\leq 1$ and $\|Wc\|_{p}\leq 1$ .

Theorem 5.1 .

There exists $\kappa,s=m^{o(1)}$ such that there exists a randomized algorithm that maintains a collection of $s$ spanning trees $\{T_{i}\}$ and solves the $\kappa$ -apx monotone min ratio cycle problem in $(m+Q)m^{o(1)}$ time, where $Q$ is the number of updates.

•

Input: Target ratio $\alpha>0$ , graph $G$ with edge gradients $g$ and lengths $\ell$
•

Updates: Edge insertions, length increases
•

Ratio of a circulation: $r(c)=\frac{\langle g,c\rangle}{\|Lc\|_{1}}$ , optimal ratio over all circulations in current graph is $r^{*}=\min_{c}r(c)$
•
Output: Either
1. 1.
  
  Certificate : if $r^{*}>-\alpha$ , any circulation $c$ ,
2. 2.
  
  Improvement : if $r^{*}\leq-\alpha$ , a circulation $c$ such that $r(c)\leq-\alpha/\kappa$ .

Theorem 6.1 .

There is an algorithm for the hidden stable flow chasing updates problem (wtf are these names) which outputs a circulation $\Delta$ such that

\frac{\langle g^{(t)},\Delta\rangle}{\|L^{(t)}\Delta\|_{1}}\leq\kappa\cdot% \frac{\langle g^{(t)},c^{(t)}\rangle}{(d+1)\|w^{(t)}\|_{1}}

Theorem 1.1 .

There is an algorithm which solves incremental max flow whp in amortized $n^{o(1)}\varepsilon^{-3}$ time per update, against adaptive adversaries.

•

Input: Vertex set $V$ , two vertices $s,t\in V$ , parameter $\varepsilon>0$ .
•

Updates: A sequence of $m\leq\operatorname{poly}(n)$ edge insertions, each with a capacity $u_{e}\in[1,U]$ .
•

Output: Maintain a $(1+\varepsilon)$ -apx maximum flow through the updates.

Proof.

Initially compute a max flow $f$ in almost-linear time. Suppose the congestion of $f$ is $C$ . We will construct a data structure that, after each edge insertion, answers

1.

Certificate : the congestion of the optimal flow has not fallen below $C^{\prime}=e^{-\varepsilon}C$ , or
2.

Improvement : returns a flow $f^{\prime}$ which has congestion less than $e^{-\varepsilon/2}C$ .

In the first case, the previously calculated $f$ is still a $(1+\varepsilon)$ -apx max flow. In the second case, we recompute a new maxflow using the static algorithm. Since the congestion drops by a $(1-\varepsilon/2)$ -factor each time, this recomputation happens only $\widetilde{O}(1/\varepsilon)$ times.

The required data structure is as follows. Initialize Theorem 2.1 with $p=2\log(2m)/\varepsilon$ , $F=m(C^{\prime})^{p}$ and error parameter $=m(C^{\prime})^{p}$ . The two cases are:

1.

The algorithm correctly certifies that $OPT>F$ . Then every flow has $\ell_{p}$ -norm at least $F$ . If there was a flow with congestion $<C^{\prime}$ , then it would also have $\ell_{p}$ -norm $<m(C^{\prime})^{p}$ . Thus $f$ is still a $(1-\varepsilon)$ -apx max flow.
2.

The algorithm returns a new flow with $\mathcal{E}(f)\leq 2m(C^{\prime})^{p}$ . Then congestion of the flow is at most $(2m)^{1/p}e^{-\varepsilon}C$ . Since $(2m)^{1/p}\leq e^{\varepsilon/2}$ from $p\geq 2\log(2m)/\varepsilon$ , this is $e^{-\varepsilon/2}C$ . Thus the congestion has dropped by a $(1-O(\varepsilon))$ factor.

∎

Theorem 2.1 .

•

Input: An $\ell_{p}$ -norm flow instance with $(G,w^{G},d)$ , threshold $F$ , parameter $\varepsilon$ .
•

Updates: Edge insertions (with corresponding $w^{G}$ )
•

Output: Either certify correctly that $OPT>F$ , or return a feasible flow $f$ with $\mathcal{E}(f)\leq F+\varepsilon$ .

where the $\ell_{p}$ -norm flow problem is

•

Input: Undirected graph $G$ , edge weights $w^{G}\geq 0$ , demand vector $d\in\mathbb{R}^{V}$ .
•

Output: minimize $\mathcal{E}(f)=\left\lVert W^{G}f\right\rVert_{p}^{p}$ over all flows $B^{\mkern-1.5mu\mathsf{T}}f=d$ .

Proof.

Let $f^{(0)}$ be the first flow computed. We run the algorithm for Theorem 3.1 iteratively $S=\frac{\lambda}{\beta}\cdot\log\left(\frac{\mathcal{E}(f^{(0)})-F}{% \varepsilon}\right)$ many times. Either

1.

It certifies at time $t$ that the flow $f^{(t)}$ satisfies for all circulations $c$ , $\mathcal{R}_{f^{(t)}}(c)>-\hat{R}=\frac{F-\mathcal{E}(f^{(t)})}{\lambda}$ . By Lemma 2.3 , $OPT>F$ .

The flow $f^{(S)}$ is returned. This means that the flow has been augmented $S$ times. By Lemma 2.4 ,

\mathcal{E}(f^{(S)})-F\leq\left(1-\beta/\lambda\right)^{S}\cdot(\mathcal{E}(f^% {(0)})-F)\leq\varepsilon

where the last inequality is by plugging in $x=\frac{\beta S}{\lambda}$ and $n=S$ in $(1+\frac{x}{n})^{n}\leq e^{x}$ (for $n\geq 1$ and $|x|\leq n$ ).

∎

Lemma 2.2 .

For any $f$ and $x$ , energy drops by at least the residual when adding circulation $x$

\mathcal{E}(f+x)-\mathcal{E}(f)\leq\mathcal{R}_{f}(x)

and there is some amount of the circulation that can be added, where the energy doesn’t drop by too much

\mathcal{E}(f+\lambda x)-\mathcal{E}(f)\geq\lambda\mathcal{R}_{f}(x)

for some $\lambda=O(p)$ .

Lemma 2.3 .

Proof.

We will show the converse. If the $p$ -norm flow instance satisfies $OPT\leq F$ , then for any flow $f$ there is a circulation $c$ such that $\mathcal{R}_{f}(c)\leq(F-\mathcal{E}(f))/\lambda$ . Let $f^{*}$ be a feasible flow with $\mathcal{E}(f^{*})\leq F$ . Then since $(f^{*}-f)/\lambda$ is a circulation, using Lemma 2.2 ,

	$\displaystyle F-\mathcal{E}(f)$	$\displaystyle\geq\mathcal{E}(f^{*})-\mathcal{E}(f)$		(since $\mathcal{E}(f^{*})\leq F$ )
		$\displaystyle\geq\lambda\mathcal{R}_{f}(f^{*}-f/\lambda)$		(by Lemma 2.2 )

∎

Lemma 2.4 .

Improvement : For any flow $f$ and any circulation $c$ such that $\mathcal{R}_{f}(c)\leq-\beta\cdot\hat{R}$ ,

\mathcal{E}(f+c)-F\leq\left(1-\frac{\beta}{\lambda}\right)\cdot\left(\mathcal{% E}(f)-F\right)

Proof.

We have

\displaystyle\mathcal{E}(f+c)-F

\displaystyle=\mathcal{E}(f+c)-\mathcal{E}(f)+\mathcal{E}(f)-F

We bound the first two terms as follows

$\displaystyle\mathcal{E}(f+c)-\mathcal{E}(f)$	$\displaystyle\leq\mathcal{R}_{f}(c)$	(by Lemma 2.2 )
	$\displaystyle\leq-\beta\cdot\hat{R}$	(by assumption)
	$\displaystyle=-\frac{\beta}{\lambda}\cdot\left(\mathcal{E}(f)-F\right)$

as required. ∎

Theorem 3.1 .

There is an algorithm for solving the $\beta$ -apx residual problem.

•

Input: an $\ell_{p}$ -norm flow instance $(G,w^{G},d)$ , a feasible flow $f$ for this instance, a threshold $F>0$ .

•

Definition: the residual threshold is $\hat{R}=\frac{\mathcal{E}(f)-F}{\lambda}$ , and the residual problem $\mathcal{R}_{f}(x)$ is

\mathcal{R}_{f}(x)=\left\langle g,x\right\rangle+\|Rx\|_{2}^{2}+\|Wx\|_{p}^{p}

•
Output: either
- –
  
  Certificate : for all circulations $c$ , $\mathcal{R}_{f}(c)\geq-\hat{R}$ .
- –
  
  Improvement : return a circulation $c$ such that $\mathcal{R}_{f}(c)\leq-\beta\cdot\hat{R}$

where $g=p(W^{G})^{p}|f|^{p-2}f,r=\sqrt{2p^{2}(W^{G})^{p}|f|^{p-2}},w=pw^{G}$ .

Proof.

Run the algorithm from Theorem 4.1 with $R^{\prime}=2\sqrt{\hat{R}}R$ and $W^{\prime}=\hat{R}^{\frac{p-1}{p}}W$ . Either

•

there is no circulation with unit negative gradient and small $2$ and $p$ norms. Then by Lemma 3.2 , every circulation satisfies $\mathcal{R}(c)>-\hat{R}$ .
•

it returns a circulation $c^{\prime}$ with unit negative gradient and approximately small $2$ and $p$ norms. Then by Lemma 3.3 , the residual of $c^{\prime}$ satisfies $\mathcal{R}(c^{\prime})\leq-(1/6K^{2})\cdot\hat{R}$ .

∎

Lemma 3.2 .

Certificate : Fix any $\hat{R}>0$ and $g, r, w$ as in the residual problem. If no circulation $c$ satisfies

\langle g,c\rangle=-1,\qquad\|2\sqrt{\hat{R}}Rc\|_{2}\leq 1,\qquad\|\hat{R}^{(% p-1)/p}Wc\|_{p}\leq 1,

then every circulation must have $\mathcal{R}(c)>-\hat{R}$ .

Proof.

We will show the converse. Let $c$ be some circulation such that $\mathcal{R}(c)\leq-\hat{R}$ . We will show that $c$ satisfies the required norm bounds. From the bound on the residual, we have

	$\displaystyle\langle g,c\rangle+\\|Rc\\|_{2}^{2}$	$\displaystyle\leq-\hat{R}$
	$\displaystyle\implies\frac{\langle g,c\rangle}{\\|Rc\\|_{2}}$	$\displaystyle\leq\frac{-\hat{R}}{\\|Rc\\|_{2}}-\\|Rc\\|_{2}$

By AM-GM, we have

\frac{1}{2}\cdot\left(\frac{\hat{R}}{\|Rc\|_{2}}+\|Rc\|_{2}\right)\geq\sqrt{% \hat{R}}

Similarly,

	$\displaystyle\langle g,c\rangle+\\|Wc\\|_{p}^{p}$	$\displaystyle\leq-\hat{R}$
	$\displaystyle\implies\frac{\langle g,c\rangle}{\\|Wc\\|_{p}}$	$\displaystyle\leq-\frac{\hat{R}}{\\|Wc\\|_{p}}-\\|Wc\\|_{p}^{p-1}$

By weighted AM-GM,

\left(\frac{p-1}{p}\right)\cdot\frac{\hat{R}}{\|Wc\|_{p}}+\frac{1}{p}\cdot\|Wc% \|_{p}^{p-1}\geq\hat{R}^{\frac{p-1}{p}}

Then setting $c^{*}=\frac{-1}{\langle g,c\rangle}\cdot c$ , we have

\langle g,c^{*}\rangle=-1,\qquad\|2\sqrt{\hat{R}}Rc\|_{2}\leq 1,\qquad\|\hat{R% }^{(p-1)/p}Wc\|_{p}\leq 1

∎

Lemma 3.3 .

Improvement : Given any $\hat{R}>0$ and an incremental $K$ -apx residual solution for $g, r, w$ , if there is a circulation $c$ with

\langle g,c\rangle=-1,\qquad\|2\sqrt{\hat{R}}Rc\|_{2}\leq K,\qquad\|\hat{R}^{(% p-1)/p}Wc\|_{p}\leq K

then for the circulation $c^{\prime}=\frac{\hat{R}}{2K^{2}}c$ ,

\mathcal{R}(c^{\prime})\leq-\frac{\hat{R}}{6K^{2}}

Proof.

The assumptions on $c$ can be restated as

\langle g,c\rangle=-1,\qquad\|Rc\|_{2}\leq\frac{K}{2\sqrt{\hat{R}}},\qquad\|Wc% \|_{p}\leq\frac{K}{\hat{R}^{(p-1)/p}}

Letting $\zeta=\frac{\hat{R}}{2K^{2}}$ ,

$\displaystyle\mathcal{R}(c^{\prime})$	$\displaystyle=\zeta\cdot\langle g,c\rangle$	$\displaystyle+\zeta^{2}\cdot\\|Rc\\|_{2}^{2}$	$\displaystyle+\zeta^{p}\cdot\\|Wc\\|_{p}^{p}$
	$\displaystyle\leq\zeta\cdot(-1)$	$\displaystyle+\zeta^{2}\cdot\frac{1}{8\zeta}$	$\displaystyle+\zeta^{p}\cdot\frac{K^{p}}{\hat{R}^{p-1}}$
	$\displaystyle\leq-\zeta$	$\displaystyle+\frac{\zeta}{8}$	$\displaystyle+\frac{\hat{R}}{2^{p}K^{p}}$
	$\displaystyle\leq-\zeta+\frac{\zeta}{8}+\frac{\zeta}{4}$
	$\displaystyle\leq-\frac{\zeta}{3}$

∎

Theorem 4.1 .

There is a randomized algorithm for the incremental $K$ -apx residual problem that runs in $m^{1+o(1)}$ time and succeeds with high probability against an adaptive adversary.

•

Input: Incremental graph $G$ with $(g,r,w)$ weights and a parameter $K\geq 1$ .
•
Output: Either
1. 1.
  
  certify that there is no circulation $c^{*}$ such that $\langle g,c^{*}\rangle=-1,\|Rc\|_{2}\leq 1$ and $\|Wc\|_{p}\leq 1$ , or
2. 2.
  
  output a circulation $c$ such that $\langle g,c^{*}\rangle=-1,\|Rc\|_{2}\leq K$ and $\|Wc\|_{p}\leq K$ .

Proof.

We run Theorem 5.1 with $\ell_{e}=K^{q-2}r_{e}^{2}a_{e}+w_{e}^{q}b_{e}^{q-1}$ (refer to paper for more notation) in that algorithm. Either

•

It returns a cycle with ratio $>-\alpha/\kappa$ : then there is no circulation with ratio $\leq-\alpha$ . Among circulations with $\langle g,c^{*}\rangle=-1$ , there is no circulation with $\|Lc^{*}\|\leq 1/\alpha=20qK^{q-1}$ . Then appeal to Lemma 4.6 .
•

The algorithm returns $c^{(T)}$ : then appeal to Lemma 4.5 or something idk.

∎

Lemma 4.2 .

Initially, $\Phi^{(0)}=K^{2}$ and $\Psi^{(0)}=K^{q}$ .

Proof.

Initially, $a^{(0)}=\frac{K}{\sqrt{m}}r^{-1}$ and $b^{(0)}=\frac{K}{m^{1/q}}w^{-1}$ . Thus $Ra^{(0)}=\frac{K}{\sqrt{m}}$ and $Wb^{(0)}=\frac{K}{m^{1/q}}$ . This gives the lemma. ∎

Lemma 4.3 .

At any iteration $i$ , $\Phi^{(i+1)}\leq\Phi^{(i)}+\frac{3K^{2}}{T}$ .

Proof.

Let $\Phi$ be the old potential and $\Phi^{\prime}$ be the new potential. The cycle $\Delta$ satisfies $\langle g,\Delta\rangle=-1$ and $\|\widetilde{L}\Delta\|_{1}\leq K^{q}$ .

We will show that $|\Delta_{e}|\leq Ta_{e}$ and $\sum_{e}r_{e}^{2}a_{e}|\Delta_{e}|\leq K^{2}$ . Then the lemma follows, since

$\displaystyle\Phi^{\prime}$	$\displaystyle=\sum_{e}r_{e}^{2}\left(a_{e}+\frac{1}{T}\|\Delta_{e}\|\right)^{2}$
	$\displaystyle=\sum_{e}r_{e}^{2}\left(a_{e}^{2}+\frac{2}{T}a_{e}\|\Delta_{e}\|+% \frac{1}{T^{2}}\|\Delta_{e}\|^{2}\right)$
	$\displaystyle\leq\sum_{e}r_{e}^{2}\left(a_{e}^{2}+\frac{2}{T}a_{e}\|\Delta_{e}\|% +\frac{1}{T}a_{e}\|\Delta_{e}\|\right)$	(since $\|\Delta_{e}\|\leq Ta_{e}$ )
	$\displaystyle=\Phi+\frac{3}{T}\sum_{e}r_{e}^{2}a_{e}\|\Delta_{e}\|$
	$\displaystyle\leq\Phi+\frac{3K^{2}}{T}$	(since $\sum_{e}r_{e}^{2}a_{e}\|\Delta_{e}\|\leq K^{2}$ )

We show the two statements required. By definition of $\ell$ ,

K^{q-2}r_{e}^{2}a_{e}|\Delta_{e}|\leq\ell_{e}|\Delta_{e}|\leq\|L\Delta\|_{1}% \leq\|\widetilde{L}\Delta\|_{1}\leq K^{q}

In particular, the first inequality gives us our second statement. Now since $a_{e}^{2}\geq K^{2}/m$ ,

\frac{K^{2}|\Delta_{e}|}{ma_{e}}\leq\frac{r_{e}^{2}a_{e}^{2}|\Delta_{e}|}{a_{e% }}=r_{e}^{2}a_{e}|\Delta_{e}|\leq K^{2}

which gives us the first statement. ∎

Lemma 4.4 .

At any iteration $i$ , $\Psi^{(i+1)}\leq\Psi^{(i)}+\frac{4qK^{q}}{T}$ .

Proof.

Something. ∎

Lemma 4.5 .

Improvement : When Algorithm 2 returns $c^{(T)}$ , we have

\Phi^{(T)}\leq 4K^{2}\qquad\text{and}\qquad\Psi^{(T)}\leq 5qK^{q}

Therefore, we have

\|Rc^{(T)}\|_{2}\leq 2K\qquad\text{and}\qquad\|Wc^{(T)}\|_{p}\leq 2K

Proof.

The first claim follows from Lemma 4.2 , Lemma 4.3 , and Lemma 4.4 . ∎

Lemma 4.6 .

Certificate : At any iteration $i$ , if there is no circulation $c$ that satisfies

\langle g,c\rangle=-1,\qquad\|L^{(i)}c\|_{1}\leq 20qK^{q-1}

then there is no circulation $c$ such that $\langle g,c\rangle=-1,\|Rc\|_{2}\leq 1$ and $\|Wc\|_{p}\leq 1$ .

Proof.

We show the converse. Let $c^{*}$ be a circulation satisfying the required properties. Then at any iteration $i$ ,

	$\displaystyle\\|Lc^{*}\\|_{1}$	$\displaystyle=K^{q-2}\sum_{e}r_{e}^{2}a_{e}\|c_{e}^{}\|+\sum_{e}w_{e}^{q}b_{e}^% {q-1}\|c_{e}^{}\|$
		$\displaystyle\leq K^{q-2}\\|Ra\\|_{2}\\|Rc^{}\\|_{2}+\\|W^{q-1}b^{q-1}\\|_{q/(q-1)}% \\|Wc^{}\\|_{q}$

We bound each term separately. First, using Lemma 4.5 ,

	$\displaystyle K^{q-2}\\|Ra\\|_{2}\\|Rc^{*}\\|_{2}$	$\displaystyle\leq K^{q-2}\cdot 2K$
		$\displaystyle\leq 2K^{q-1}\leq 10qK^{q-1}$

and

	$\displaystyle\\|W^{q-1}b^{q-1}\\|_{q/(q-1)}\\|Wc^{*}\\|_{q}$	$\displaystyle\leq\\|Wb\\|_{q}^{q-1}\cdot 2$
		$\displaystyle\leq(5qK^{q})^{\frac{q-1}{q}}\cdot 2$
		$\displaystyle\leq 10qK^{q-1}$

∎

Theorem 5.1 .

•

Input: Target ratio $\alpha>0$ , graph $G$ with edge gradients $g$ and lengths $\ell$
•

Updates: Edge insertions, length increases
•

Ratio of a circulation: $r(c)=\frac{\langle g,c\rangle}{\|Lc\|_{1}}$ , optimal ratio over all circulations in current graph is $r^{*}=\min_{c}r(c)$
•
Output: Either
1. 1.
  
  Certificate : if $r^{*}>-\alpha$ , any circulation $c$ ,
2. 2.
  
  Improvement : if $r^{*}\leq-\alpha$ , a circulation $c$ such that $r(c)\leq-\alpha/\kappa$ .

Proof.

Use the dynamic algorithm of Theorem 6.1 . Define $c^{*}$ to be any min ratio circulation in the first iteration where $r^{*}\leq-\alpha$ . Define $c^{(t)}$ to be $c^{*}$ if all edges of $c^{*}$ are in $G$ , else define $c^{(t)}$ to be the zero circulation. Define the widths $w^{(t)}$ to be $|\ell_{e}^{(t)}c_{e}^{*}|$ if $e\in\operatorname{supp}(c^{*})$ and $0$ otherwise. The conditions for hidden stable flow chasing updates holds since an edge is deleted and re-inserted when its length doubles. Either

•

Certificate : if $\operatorname{supp}(c^{*})$ is not contained in $G^{(t)}$ , then we do not care which circulation is output.

•

Improvement : if $\operatorname{supp}(c^{*})$ is supported in $G^{(t)}$ , then the output circulation satisfies

\frac{\langle g^{(t)},\Delta\rangle}{\|L^{(t)}\Delta\|_{1}}\leq\kappa\cdot% \frac{\langle g^{(t)},c^{(t)}\rangle}{(d+1)\|w^{(t)}\|_{1}}\leq\frac{\kappa}{d% +1}\cdot\frac{\langle g^{(t)},c^{*}\rangle}{\|L^{(t)}c^{*}\|_{1}}

∎

Theorem 6.1 .

There is an algorithm for the hidden stable flow chasing updates problem (wtf are these names) which outputs a circulation $\Delta$ such that

\frac{\langle g^{(t)},\Delta\rangle}{\|L^{(t)}\Delta\|_{1}}\leq\kappa\cdot% \frac{\langle g^{(t)},c^{(t)}\rangle}{(d+1)\|w^{(t)}\|_{1}}

	$\displaystyle\langle g,c\rangle+\\|Rc\\|_{2}^{2}$	$\displaystyle\leq-\hat{R}$
	$\displaystyle\implies\frac{\langle g,c\rangle}{\\|Rc\\|_{2}}$	$\displaystyle\leq\frac{-\hat{R}}{\\|Rc\\|_{2}}-\\|Rc\\|_{2}$

	$\displaystyle\langle g,c\rangle+\\|Wc\\|_{p}^{p}$	$\displaystyle\leq-\hat{R}$
	$\displaystyle\implies\frac{\langle g,c\rangle}{\\|Wc\\|_{p}}$	$\displaystyle\leq-\frac{\hat{R}}{\\|Wc\\|_{p}}-\\|Wc\\|_{p}^{p-1}$

$\displaystyle\Phi^{\prime}$	$\displaystyle=\sum_{e}r_{e}^{2}\left(a_{e}+\frac{1}{T}\|\Delta_{e}\|\right)^{2}$
	$\displaystyle=\sum_{e}r_{e}^{2}\left(a_{e}^{2}+\frac{2}{T}a_{e}\|\Delta_{e}\|+% \frac{1}{T^{2}}\|\Delta_{e}\|^{2}\right)$
	$\displaystyle\leq\sum_{e}r_{e}^{2}\left(a_{e}^{2}+\frac{2}{T}a_{e}\|\Delta_{e}\|% +\frac{1}{T}a_{e}\|\Delta_{e}\|\right)$	(since $\|\Delta_{e}\|\leq Ta_{e}$ )
	$\displaystyle=\Phi+\frac{3}{T}\sum_{e}r_{e}^{2}a_{e}\|\Delta_{e}\|$
	$\displaystyle\leq\Phi+\frac{3K^{2}}{T}$	(since $\sum_{e}r_{e}^{2}a_{e}\|\Delta_{e}\|\leq K^{2}$ )