Lemma 1.1 .

Let $G$ be a graph with weights $\{w_{e}\}$ . Then for any vector $\ell\in\mathbb{R}_{\geq 0}^{m}$ ,

\sum_{e,f\in E}\ell_{e}\ell_{f}\sqrt{w_{e}w_{f}}|b_{e}L_{G}^{\dagger}b_{f}^{% \mkern-1.5mu\mathsf{T}}|\leq\alpha_{\text{local}}\cdot\|\ell\|_{2}^{2}

Lemma 1.2 .

For any probability distribution $p\in\Delta^{m}$ , the oblivious routing $M_{w}$ corresponding to the electrical network with weights $w_{e}=\left(p_{e}+\frac{1}{m}\right)^{-1}$ satisfies $\sum_{e}p_{e}\textrm{load}_{w}(e)\leq 2\alpha_{\text{local}}$ .

Lemma 2.1 .

The matrix $\Pi$ is a projection matrix.

Lemma 2.2 .

Let $G$ be a graph with weights $\{w_{e}\}$ and let $L$ be the Laplacian matrix associated with $G$ . For any edge $e$ , we have that

\sum_{f}w_{e}w_{f}|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}|^{2}\leq 1.

Lemma 2.3 .

For any probability distribution $p\in\Delta^{m}$ , the oblivious routing $M_{w}$ corresponding to the electrical network with weights $w_{e}=\left(p_{e}+\frac{1}{m}\right)^{-1}$ satisfies $\textrm{load}_{w}(e)\leq\sqrt{2m}$ for every edge $e$ .

Theorem 3.1 .

There is an algorithm ApproxLapSolve that gets as input a Laplacian $L$ of an $n$ -vertex $m$ -edge graph, a vector $y\in\mathbb{R}^{n}$ , error bound $\epsilon_{L}$ , and returns a vector $x\in\mathbb{R}^{n}$ such that the following holds with probability $\geq 1-\frac{1}{poly(n)}$ .

\|x-L^{\dagger}y\|_{L}\leq\epsilon_{L}\cdot\|L^{\dagger}y\|_{L}

where $\|x\|_{L}=\sqrt{x^{\mkern-1.5mu\mathsf{T}}Lx}$ is the norm induced by the Laplacian. Further, the algorithm runs in time $\widetilde{O}(m\log(1/\epsilon_{L}))$ .

Theorem 3.2 .

Given $m\in\mathbb{Z}_{\geq 1}$ , $\delta\in(0,1)$ , and $\epsilon\in(0,1)$ , there is a sketch matrix $C=\text{SketchMatrix}(m,\delta,\epsilon)\in\mathbb{R}^{\ell\times m}$ and an algorithm $\text{RecoverNorm}(s)$ for $s\in\mathbb{R}^{\ell}$ such that the following properties hold:

•

(Approximation) For any $v\in\mathbb{R}^{m}$ , with probability at least $1-\delta$ over the randomness of SketchMatrix , the value of $r=\text{RecoverNorm}(Cv)$ is

(1-\epsilon)\|v\|_{1}\leq r\leq(1+\epsilon)\|v\|_{1}

•

$\ell=c/\epsilon^{2}\cdot\log(1/\delta)$ for some constant $c>1$
•

(running time) SketchMatrix and RecoverNorm take time $O(\ell m)$ and $poly(\ell)$ respectively.

Lemma 3.3 .

For any weighted graph $(G,w)$ , the load on any edge $e$ has the following lower bound.

\textrm{load}_{w}(e)\geq\frac{2w_{e}}{nw_{\max}},

where $w_{\max}$ is the maximum edge weight.

Lemma 3.4 .

For any $x\in\mathbb{R}^{n}$ such that $x\perp 1$ , we have $n^{-2}\cdot\|x\|_{\infty}\leq\|x\|_{L}$ .

Lemma 3.5 .

For any $x\in\mathbb{R}^{n}$ , $\|x\|_{L}\leq 2n\cdot\|x\|_{\infty}$ .

Lemma 3.6 .

Suppose we have two vectors $x,y\in\mathbb{R}^{n}$ such that $x,y\perp 1$ and $\|x-y\|_{L}\leq\epsilon\|y\|_{L}$ . Then $\|x-y\|_{\infty}\leq\epsilon\cdot 2n^{3}\cdot\|y\|_{\infty}$ .

Lemma 3.7 .

Let $U$ be an $n\times\ell$ matrix, with $K$ being the largest value present in the matrix. Let $\widetilde{U}$ be an approximation of $U$ such that for every $j\in[\ell]$ , the $j$ -th column $\widetilde{C}_{j}$ of $\widetilde{U}$ is $\epsilon$ -close to the $j$ -th column $C_{j}$ of $U$ in the following sense: $\forall j\in[\ell],\|\widetilde{C}_{j}-C_{j}\|_{\infty}\leq\epsilon\cdot\|C_{j% }\|_{\infty}$ . Then for any $i\in[n]$ , and rows $R_{i}$ of $U$ and $\widetilde{R}_{i}$ of $\widetilde{U}$ ,

\|\widetilde{R}_{i}-R_{i}\|_{\infty}\leq\epsilon\cdot K

Lemma 3.8 .

Let $x,y\in\mathbb{R}^{\ell}$ be such that $\|x-y\|_{\infty}\leq\epsilon$ , where $\ell$ is odd. Then

\text{median}(|x_{1}|,|x_{2}|,\ldots,|x_{\ell}|)-\epsilon\leq\text{median}(|y_% {1}|,|y_{2}|,\ldots,|y_{\ell}|)\leq\text{median}(|x_{1}|,|x_{2}|,\ldots,|x_{% \ell}|)+\epsilon

Lemma 3.9 .

Let $a\in\mathbb{R}$ be a real number. Suppose $x\in\mathbb{R}^{\ell}$ satisfies

(1-\epsilon)\cdot a\leq\text{median}(|x_{1}|,|x_{2}|,\ldots,|x_{\ell}|)\leq(1+% \epsilon)\cdot a

Suppose $y\in\mathbb{R}^{\ell}$ is such that $\|x-y\|_{\infty}\leq\epsilon^{\prime}$ , then $y$ satisfies

(1-\epsilon)\cdot a-\epsilon^{\prime}\leq\text{median}(|y_{1}|,|y_{2}|,\ldots,% |y_{\ell}|)\leq(1+\epsilon)\cdot a+\epsilon^{\prime}

Lemma 3.10 .

For any approximation factor $0<\epsilon<1$ , and any weighted graph $(G,w)$ , let $\textrm{load}_{w}=\left(w_{e}\sum_{f}|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu% \mathsf{T}}|\right)_{e\in E}$ be the true loads, and $\textrm{aload}_{w}=\text{GetApproxLoad}(G,w,\epsilon)$ be the approximate loads computed by the algorithm when using an approximate Laplacian solver. Then with probability $\geq 1-\frac{1}{poly(n)}$ ,

(1-\epsilon)\cdot\textrm{load}_{w}(e)\leq\textrm{aload}_{w}(e)\leq(1+\epsilon)% \cdot\textrm{load}_{w}(e)\qquad\text{for all $e\in E$}

Lemma 4.1 .

For any $t\geq 1$ , $\|x^{(t)}\|_{1}\leq\|x^{(t-1)}\|_{1}\cdot\exp(2\alpha_{\text{local}}/\rho)$ . At the end of the algorithm, $\|x^{(T)}\|_{1}\leq m\cdot\exp(2\alpha_{\text{local}}T/\rho)$ .

Lemma 4.2 .

Let $M^{*}$ be the routing returned by the algorithm. For any edge $e$ ,

x_{e}^{(T)}\geq\exp\left(\frac{T}{8\rho}\cdot\textrm{load}_{M^{*}}(e)\right).

Lemma 4.3 .

The routing returned by the algorithm has competitive ratio $O(\alpha_{\text{local}})$ .

Lemma 1.1 .

Let $G$ be a graph with weights $\{w_{e}\}$ . Then for any vector $\ell\in\mathbb{R}_{\geq 0}^{m}$ ,

\sum_{e,f\in E}\ell_{e}\ell_{f}\sqrt{w_{e}w_{f}}|b_{e}L_{G}^{\dagger}b_{f}^{% \mkern-1.5mu\mathsf{T}}|\leq\alpha_{\text{local}}\cdot\|\ell\|_{2}^{2}

Lemma 1.2 .

Proof.

Setting $\ell_{e}$ to $\frac{1}{\sqrt{w_{e}}}$ and applying Lemma 1.1 , we get

$\displaystyle\sum_{e}p_{e}\textrm{load}_{w}(e)$	$\displaystyle=\sum_{e}p_{e}\sum_{f}\textrm{load}_{w}(f\to e)$
	$\displaystyle=\sum_{e}p_{e}\cdot w_{e}\cdot\sum_{f}\|b_{e}L^{\dagger}b_{f}^{% \mkern-1.5mu\mathsf{T}}\|$	(by definition of load)
	$\displaystyle=\sum_{e}p_{e}\cdot\left(p_{e}+\frac{1}{m}\right)^{-1}\cdot\sum_{% f}\|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|$	(by definition of $w_{e}$ )
	$\displaystyle\leq\sum_{e}\sum_{f}\|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T% }}\|$
	$\displaystyle=\sum_{e,f}\frac{1}{\sqrt{w_{e}w_{f}}}\cdot\sqrt{w_{e}w_{f}}\cdot% \|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|$
	$\displaystyle=\sum_{e,f}\ell_{e}\ell_{f}\cdot\sqrt{w_{e}w_{f}}\cdot\|b_{e}L^{% \dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|$	(by choice of $\ell_{e}$ )
	$\displaystyle\leq\alpha_{\text{local}}\cdot\\|\ell\\|_{2}^{2}$	(by Lemma 1.1 )
	$\displaystyle=\alpha_{\text{local}}\cdot\sum_{e}\frac{1}{w_{e}}$
	$\displaystyle=\alpha_{\text{local}}\cdot\sum_{e}\left(p_{e}+\frac{1}{m}\right)$
	$\displaystyle=2\alpha_{\text{local}},$

as required. ∎

Lemma 2.1 .

The matrix $\Pi$ is a projection matrix.

Proof.

We show that $\Pi^{2}=\Pi$ .

	$\displaystyle\Pi^{2}$	$\displaystyle=\left(W^{\frac{1}{2}}BL^{\dagger}B^{\mkern-1.5mu\mathsf{T}}W^{% \frac{1}{2}}\right)\cdot\left(W^{\frac{1}{2}}BL^{\dagger}B^{\mkern-1.5mu% \mathsf{T}}W^{\frac{1}{2}}\right)$
		$\displaystyle=\left(W^{\frac{1}{2}}B\right)\cdot\left(L^{\dagger}B^{\mkern-1.5% mu\mathsf{T}}WBL^{\dagger}\right)\cdot\left(B^{\mkern-1.5mu\mathsf{T}}W^{\frac% {1}{2}}\right)$
		$\displaystyle=\left(W^{\frac{1}{2}}B\right)\cdot L^{\dagger}\cdot\left(B^{% \mkern-1.5mu\mathsf{T}}W^{\frac{1}{2}}\right)=\Pi.$

as required. ∎

Lemma 2.2 .

Let $G$ be a graph with weights $\{w_{e}\}$ and let $L$ be the Laplacian matrix associated with $G$ . For any edge $e$ , we have that

\sum_{f}w_{e}w_{f}|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}|^{2}\leq 1.

Proof.

By Lemma 2.1 we know that $\Pi$ is a projection matrix. This in particular implies that the diagonal entries of $\Pi$ (and hence $\Pi^{2}$ ) are less then $1$ . Thus,

	$\displaystyle\sum_{f}w_{e}w_{f}\|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}% \|^{2}$	$\displaystyle=\sum_{f}\left(\sqrt{w_{e}w_{f}}\cdot\|b_{e}L^{\dagger}b_{f}^{% \mkern-1.5mu\mathsf{T}}\|\right)^{2}$
		$\displaystyle=\sum_{f}\Pi(e,f)^{2}$
		$\displaystyle=\Pi^{2}(e,e)\leq 1,$

which was what we were after. ∎

Lemma 2.3 .

For any probability distribution $p\in\Delta^{m}$ , the oblivious routing $M_{w}$ corresponding to the electrical network with weights $w_{e}=\left(p_{e}+\frac{1}{m}\right)^{-1}$ satisfies $\textrm{load}_{w}(e)\leq\sqrt{2m}$ for every edge $e$ .

Proof.

Fixing an edge $e$ ,

$\displaystyle\textrm{load}_{w}(e)$	$\displaystyle=w_{e}\sum_{f}\|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|$
	$\displaystyle\leq\sum_{f}\sqrt{\frac{w_{e}}{w_{f}}}\cdot\sqrt{w_{e}w_{f}}\|b_{e% }L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|$
	$\displaystyle\leq\sqrt{\sum_{f}\frac{w_{e}}{w_{f}}}\cdot\sqrt{\sum_{f}w_{e}w_{% f}\|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|^{2}}$	(by Cauchy-Schwarz)

We now bound each of the two terms separately. For the first term, note that

	$\displaystyle w_{e}\cdot\sum_{f}\frac{1}{w_{f}}$	$\displaystyle=\left(p_{e}+\frac{1}{m}\right)^{-1}\cdot\sum_{f}\left(p_{f}+% \frac{1}{m}\right)$
		$\displaystyle\leq 2\cdot\left(p_{e}+\frac{1}{m}\right)^{-1}$
		$\displaystyle\leq 2\cdot\frac{1}{\left(\frac{1}{m}\right)}=2m.$

For the second term, by Lemma 2.2 , we know that

\sum_{f}w_{e}w_{f}|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}|^{2}\leq 1.

Putting these two inequalities together, we get that $\textrm{load}_{w}(e)\leq\sqrt{2m}$ for any edge $e$ , which gives the desired bound of $\sqrt{2m}$ on the width. ∎

Theorem 3.1 .

\|x-L^{\dagger}y\|_{L}\leq\epsilon_{L}\cdot\|L^{\dagger}y\|_{L}

where $\|x\|_{L}=\sqrt{x^{\mkern-1.5mu\mathsf{T}}Lx}$ is the norm induced by the Laplacian. Further, the algorithm runs in time $\widetilde{O}(m\log(1/\epsilon_{L}))$ .

Theorem 3.2 .

•

(Approximation) For any $v\in\mathbb{R}^{m}$ , with probability at least $1-\delta$ over the randomness of SketchMatrix , the value of $r=\text{RecoverNorm}(Cv)$ is

(1-\epsilon)\|v\|_{1}\leq r\leq(1+\epsilon)\|v\|_{1}

•

$\ell=c/\epsilon^{2}\cdot\log(1/\delta)$ for some constant $c>1$
•

(running time) SketchMatrix and RecoverNorm take time $O(\ell m)$ and $poly(\ell)$ respectively.

Lemma 3.3 .

For any weighted graph $(G,w)$ , the load on any edge $e$ has the following lower bound.

\textrm{load}_{w}(e)\geq\frac{2w_{e}}{nw_{\max}},

where $w_{\max}$ is the maximum edge weight.

Lemma 3.4 .

For any $x\in\mathbb{R}^{n}$ such that $x\perp 1$ , we have $n^{-2}\cdot\|x\|_{\infty}\leq\|x\|_{L}$ .

Proof.

Since $\min_{x\in\mathbb{R}^{n}}\|x\|_{L}^{2}/\|x\|_{2}^{2}=0$ which is attained by $1$ , by the variational characterization of eigenvalues of a symmetric matrix, the second smallest eigenvalue $\lambda_{2}$ of $L$ is given by

\min_{x\in\mathbb{R}^{n}:x\perp 1}\frac{\|x\|_{L}^{2}}{\|x\|_{2}^{2}}=\lambda_% {2}

By Cheeger’s inequality, $\lambda_{2}\geq h^{2}/2\Delta$ , where $h=\min_{S:|S|\leq n/2}|E(S,\overline{S})|/|S|$ is the unnormalized Cheeger’s constant and $\Delta$ is the maximum degree in the graph. Thus

\lambda_{2}\geq h^{2}\cdot\frac{1}{2\Delta}\geq\frac{4}{n^{2}}\cdot\frac{1}{2n% }\geq n^{-3}

Thus for any $x\in\mathbb{R}^{n}$ such that $x\perp 1$ , $\|x\|_{L}\geq n^{-3/2}\cdot\|x\|_{2}\geq n^{-3/2}\cdot\|x\|_{\infty}$ , and the lemma follows. ∎

Lemma 3.5 .

For any $x\in\mathbb{R}^{n}$ , $\|x\|_{L}\leq 2n\cdot\|x\|_{\infty}$ .

Proof.

Since $\|x\|_{\infty}^{2}\leq 1$ implies $|x_{i}|\leq 1$ for all $i\in[n]$ , and since $\|x\|_{L}^{2}=x^{\mkern-1.5mu\mathsf{T}}Lx$ , we have

\max_{x\in\mathbb{R}^{n}}\frac{\|x\|_{L}^{2}}{\|x\|_{\infty}^{2}}\leq\max_{x% \in\mathbb{R}^{n}:|x_{i}|\leq 1}x^{\mkern-1.5mu\mathsf{T}}Lx

Since $x^{\mkern-1.5mu\mathsf{T}}Lx=\sum_{(u,v)\in E}(x_{u}-x_{v})^{2}$ , and $|x_{i}|\leq 1,$ each term is bounded by 4. Thus, the sum is at most $4m\leq 4n^{2},$ giving the lemma. ∎

Lemma 3.6 .

Suppose we have two vectors $x,y\in\mathbb{R}^{n}$ such that $x,y\perp 1$ and $\|x-y\|_{L}\leq\epsilon\|y\|_{L}$ . Then $\|x-y\|_{\infty}\leq\epsilon\cdot 2n^{3}\cdot\|y\|_{\infty}$ .

Proof.

By Lemmas 3.5 and 3.4 , we have

n^{-2}\cdot\|x-y\|_{\infty}\leq\|x-y\|_{L}\qquad\text{and}\qquad\|y\|_{L}\leq 2% n\cdot\|y\|_{\infty}

Together with the assumption in our lemma, we get

\|x-y\|_{\infty}\leq n^{2}\cdot\|x-y\|_{L}\leq\epsilon\cdot n^{2}\cdot\|y\|_{L% }\leq\epsilon\cdot 2n^{3}\cdot\|y\|_{\infty}

as claimed. ∎

Lemma 3.7 .

\|\widetilde{R}_{i}-R_{i}\|_{\infty}\leq\epsilon\cdot K

Proof.

For any $i\in[n]$ ,

	$\displaystyle\\|\widetilde{R}_{i}-R_{i}\\|_{\infty}$	$\displaystyle\leq\max_{i\in[n]}\\|\widetilde{R}_{i}-R_{i}\\|_{\infty}$
		$\displaystyle=\max_{i,j\in[n]\times[\ell]}\|\widetilde{U}_{ij}-U_{ij}\|$
		$\displaystyle=\max_{j\in[\ell]}\\|\widetilde{C}_{j}-C_{j}\\|_{\infty}$
		$\displaystyle\leq\epsilon\cdot\max_{j\in[\ell]}\\|C_{j}\\|_{\infty}$
		$\displaystyle\leq\epsilon\cdot K$

as required. ∎

Lemma 3.8 .

Let $x,y\in\mathbb{R}^{\ell}$ be such that $\|x-y\|_{\infty}\leq\epsilon$ , where $\ell$ is odd. Then

\text{median}(|x_{1}|,|x_{2}|,\ldots,|x_{\ell}|)-\epsilon\leq\text{median}(|y_% {1}|,|y_{2}|,\ldots,|y_{\ell}|)\leq\text{median}(|x_{1}|,|x_{2}|,\ldots,|x_{% \ell}|)+\epsilon

Proof.

Note that if $|x_{i}-y_{i}|\leq\epsilon$ , then $||x_{i}|-|y_{i}||\leq\epsilon$ as well. Thus we can assume without loss of generality that $x$ and $y$ are non-negative.

Relabel the indices such that $x_{1}\leq x_{2}\leq\ldots\leq x_{\ell}$ are in non-decreasing order. The assumption on $\ell_{\infty}$ norm gives us that for all $i\in[\ell]$ ,

|x_{i}-y_{i}|\leq\epsilon

(3.1)

Let $\pi$ be a permutation such that $y_{\pi(1)}\leq y_{\pi(2)}\leq\ldots\leq y_{\pi(\ell)}$ is in non-decreasing order. Let $m=\left\lceil\ell/2\right\rceil$ . We want to show that $|y_{\pi(m)}-x_{m}|\leq\epsilon$ . If $m=\pi(m)$ , then the lemma follows from Equation 3.1 with $i=m$ . So assume that $m\neq\pi(m)$ .

Consider the case when $m>\pi(m)$ . Then since $y_{m}\geq y_{\pi(m)}$ , we have $x_{m}\geq y_{m}-\epsilon\geq y_{\pi(m)}-\epsilon$ . For the other direction, since $m>\pi(m)$ , there exists an index $j$ such that $x_{j}>x_{m}$ and $y_{j}\leq y_{\pi(m)}$ . For this index, we have $y_{\pi(m)}\geq y_{j}\geq x_{j}-\epsilon\geq x_{m}-\epsilon$ as required. The case when $m<\pi(m)$ is symmetric. ∎

Lemma 3.9 .

Let $a\in\mathbb{R}$ be a real number. Suppose $x\in\mathbb{R}^{\ell}$ satisfies

(1-\epsilon)\cdot a\leq\text{median}(|x_{1}|,|x_{2}|,\ldots,|x_{\ell}|)\leq(1+% \epsilon)\cdot a

Suppose $y\in\mathbb{R}^{\ell}$ is such that $\|x-y\|_{\infty}\leq\epsilon^{\prime}$ , then $y$ satisfies

(1-\epsilon)\cdot a-\epsilon^{\prime}\leq\text{median}(|y_{1}|,|y_{2}|,\ldots,% |y_{\ell}|)\leq(1+\epsilon)\cdot a+\epsilon^{\prime}

Proof.

Using Lemma 3.8 and the assumption on $x$ ,

	$\displaystyle(1-\epsilon)\cdot a-\epsilon^{\prime}$	$\displaystyle\leq\text{median}(\|x_{1}\|,\|x_{2}\|,\ldots,\|x_{\ell}\|)-\epsilon^{\prime}$
		$\displaystyle\leq\text{median}(\|y_{1}\|,\|y_{2}\|,\ldots,\|y_{\ell}\|)$
		$\displaystyle\leq\text{median}(\|x_{1}\|,\|x_{2}\|,\ldots,\|x_{\ell}\|)+\epsilon^{\prime}$
		$\displaystyle\leq(1+\epsilon)\cdot a+\epsilon^{\prime}$

as required. ∎

Lemma 3.10 .

(1-\epsilon)\cdot\textrm{load}_{w}(e)\leq\textrm{aload}_{w}(e)\leq(1+\epsilon)% \cdot\textrm{load}_{w}(e)\qquad\text{for all $e\in E$}

Proof.

Let $U=L^{\dagger}B^{\mkern-1.5mu\mathsf{T}}C^{\mkern-1.5mu\mathsf{T}}$ , and $\widetilde{U}=\text{ApproxLapSolve}(L,B^{\mkern-1.5mu\mathsf{T}}C^{\mkern-1.5% mu\mathsf{T}},\delta,\epsilon_{L})$ where we abuse notation to mean that ApproxLapSolve runs on each column of $B^{\mkern-1.5mu\mathsf{T}}C^{\mkern-1.5mu\mathsf{T}}$ and returns a column vector. Let $R_{i}$ and $\widetilde{R}_{i}$ denote the rows, and $C_{j}$ and $\widetilde{C}_{j}$ denote the columns of $U$ and $\widetilde{U}$ respectively. By guarantees of the approximate Laplacian solver, we have

\|\widetilde{C}_{j}-C_{j}\|_{L}\leq\epsilon_{L}\|C_{j}\|_{L}

Lemma 3.6 tells us that

\|\widetilde{C}_{j}-C_{j}\|_{\infty}\leq\epsilon_{L}\cdot 2n^{3}\cdot\|C_{j}\|% _{\infty}

With $K$ as an upper bound on the maximum entry in $CBL^{\dagger}$ , and using the above inequality in Lemma 3.7 , we get that

\|\widetilde{R}_{i}-R_{i}\|_{\infty}\leq\epsilon_{L}\cdot 2n^{3}\cdot K

Note that for any $e=(u,v)$ , $(U^{\mkern-1.5mu\mathsf{T}}b_{e})^{\mkern-1.5mu\mathsf{T}}=R_{u}-R_{v}$ , and $(\widetilde{U}^{\mkern-1.5mu\mathsf{T}}b_{e})^{\mkern-1.5mu\mathsf{T}}=% \widetilde{R}_{u}-\widetilde{R}_{v}$ . Thus

	$\displaystyle\\|(U^{\mkern-1.5mu\mathsf{T}}b_{e})-(\widetilde{U}^{\mkern-1.5mu% \mathsf{T}}b_{e})\\|_{\infty}$	$\displaystyle=\\|(R_{u}-R_{v})-(\widetilde{R}_{u}-\widetilde{R}_{v})\\|_{\infty}$
		$\displaystyle\leq\\|R_{u}-\widetilde{R}_{u}\\|_{\infty}+\\|R_{v}-\widetilde{R}_{v% }\\|_{\infty}$
		$\displaystyle\leq 4\epsilon n^{3}K$

By choice of $\epsilon_{L}=\frac{\epsilon}{(8mn^{4}K)}$ , the final expression is $\frac{\epsilon}{2mn}$ . Since $\text{RecoverNorm}(x_{1},x_{2},\ldots,x_{\ell})=\text{median}(|x_{1}|,|x_{2}|,% \ldots,|x_{\ell}|)$ , and since the guarantees of RecoverNorm from Theorem 3.2 gives us

\left(1-\frac{\epsilon}{2}\right)\cdot\sum_{f}|b_{e}L^{\dagger}b_{f}^{\mkern-1% .5mu\mathsf{T}}|\leq\text{RecoverNorm}(U^{\mkern-1.5mu\mathsf{T}}b_{e})\leq% \left(1+\frac{\epsilon}{2}\right)\cdot\sum_{f}|b_{e}L^{\dagger}b_{f}^{\mkern-1% .5mu\mathsf{T}}|,

using Lemma 3.9 on $U^{\mkern-1.5mu\mathsf{T}}b_{e}$ and $\widetilde{U}^{\mkern-1.5mu\mathsf{T}}b_{e}$ , we get

\left(1-\frac{\epsilon}{2}\right)\cdot\sum_{f}|b_{e}L^{\dagger}b_{f}^{\mkern-1% .5mu\mathsf{T}}|-\frac{\epsilon}{2mn}\leq\text{RecoverNorm}(\widetilde{U}^{% \mkern-1.5mu\mathsf{T}}b_{e})\leq\left(1+\frac{\epsilon}{2}\right)\cdot\sum_{f% }|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}|+\frac{\epsilon}{2mn}.

Thus,

\left(1-\frac{\epsilon}{2}\right)\cdot\textrm{load}_{w}(e)-\frac{\epsilon w_{e% }}{2mn}\leq\text{GetApproxLoad}(G,w)\leq\left(1+\frac{\epsilon}{2}\right)\cdot% \textrm{load}_{w}(e)+\frac{\epsilon w_{e}}{2mn}

Since for any edge $f\in E,$ we have $w_{f}=\left(p_{f}+\frac{1}{m}\right)^{-1}\leq m$ , we get $w_{\max}\leq m.$ Thus, Lemma 3.3 gives us that $\textrm{load}_{w}(e)\geq\frac{w_{e}}{mn},$ which proves our lemma. ∎

Lemma 4.1 .

For any $t\geq 1$ , $\|x^{(t)}\|_{1}\leq\|x^{(t-1)}\|_{1}\cdot\exp(2\alpha_{\text{local}}/\rho)$ . At the end of the algorithm, $\|x^{(T)}\|_{1}\leq m\cdot\exp(2\alpha_{\text{local}}T/\rho)$ .

Proof.

The implication for $\|x^{(T)}\|_{1}$ follows from the former statement and noting that $\|x^{(0)}\|_{1}=m$ . For any $t\geq 1$ , we have

$\displaystyle\\|x^{(t)}\\|_{1}$	$\displaystyle=\sum_{e}x_{e}^{(t)}=\sum_{e}x_{e}^{(t-1)}\cdot\left(1+\frac{1}{2% \rho}\cdot\textrm{aload}_{w^{(t)}}(e)\right)$
	$\displaystyle=\sum_{e}x_{e}^{(t-1)}+\frac{1}{2\rho}\cdot\sum_{e}x_{e}^{(t-1)}% \cdot\textrm{aload}_{w^{(t)}}(e)$
	$\displaystyle\leq\sum_{e}x_{e}^{(t-1)}+\frac{\\|x^{(t-1)}\\|_{1}}{\rho}\cdot\sum% _{e}\frac{x_{e}^{(t-1)}}{\\|x^{(t-1)}\\|_{1}}\cdot\textrm{load}_{w^{(t)}}(e)$	(by Lemma 3.10 )
	$\displaystyle\leq\\|x^{(t-1)}\\|_{1}+\frac{\\|x^{(t-1)}\\|_{1}}{\rho}\cdot 2\alpha% _{\text{local}}$	(by Lemma 1.2 )
	$\displaystyle\leq\\|x^{(t-1)}\\|_{1}\cdot\exp\left(\frac{2\alpha_{\text{local}}}% {\rho}\right)$

∎

Lemma 4.2 .

Let $M^{*}$ be the routing returned by the algorithm. For any edge $e$ ,

x_{e}^{(T)}\geq\exp\left(\frac{T}{8\rho}\cdot\textrm{load}_{M^{*}}(e)\right).

Proof.

For any edge $e$ and $t\geq 1$ , we have

$\displaystyle x_{e}^{(t)}$	$\displaystyle=\prod_{t^{\prime}=1}^{t}\left(1+\frac{1}{2\rho}\cdot\textrm{% aload}_{w^{(t^{\prime})}}(e)\right)$
	$\displaystyle\geq\prod_{t^{\prime}=1}^{t}\left(1+\frac{1}{4\rho}\cdot\textrm{% load}_{w^{(t^{\prime})}}(e)\right)$	(by Lemma 3.10 )
	$\displaystyle\geq\prod_{t^{\prime}=1}^{t}\exp\left(\frac{1}{8\rho}\cdot\textrm% {load}_{w^{(t^{\prime})}}(e)\right)$	(since $e^{x}\leq 1+2x$ for $0<x<1$ , and Lemma 2.3 )
	$\displaystyle=\exp\left(\frac{1}{8\rho}\cdot\sum_{t^{\prime}=1}^{t}\textrm{% load}_{w^{(t^{\prime})}}(e)\right)$

In particular, for $t=T$ , we have

	$\displaystyle x_{e}^{(T)}$	$\displaystyle\geq\exp\left(\frac{1}{8\rho}\cdot\sum_{t^{\prime}=1}^{T}\textrm{% load}_{w^{(t^{\prime})}}(e)\right)$
		$\displaystyle\geq\exp\left(\frac{T}{8\rho}\cdot\textrm{load}_{M^{*}}(e)\right)$		(by convexity of load)

∎

Lemma 4.3 .

The routing returned by the algorithm has competitive ratio $O(\alpha_{\text{local}})$ .

Proof.

Combining Lemmas 4.1 and 4.2 , for any edge $e$ ,

\displaystyle m\exp\left(\frac{2\alpha_{\text{local}}T}{\rho}\right)

\displaystyle\geq\|x^{(T)}\|_{1}\geq x_{e}^{(T)}\geq\exp\left(\frac{T}{8\rho}% \cdot\textrm{load}_{M^{*}}(e)\right)

which in particular gives the required upper bound on $\textrm{load}_{M^{*}}(e)$ for any edge $e$ , since

	$\displaystyle\textrm{load}_{M^{*}}(e)$	$\displaystyle\leq 16\alpha_{\text{local}}+\frac{8\rho\log m}{T}$
		$\displaystyle=O(\alpha_{\text{local}})$

∎

$\displaystyle\textrm{load}_{w}(e)$	$\displaystyle=w_{e}\sum_{f}\|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|$
	$\displaystyle\leq\sum_{f}\sqrt{\frac{w_{e}}{w_{f}}}\cdot\sqrt{w_{e}w_{f}}\|b_{e% }L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|$
	$\displaystyle\leq\sqrt{\sum_{f}\frac{w_{e}}{w_{f}}}\cdot\sqrt{\sum_{f}w_{e}w_{% f}\|b_{e}L^{\dagger}b_{f}^{\mkern-1.5mu\mathsf{T}}\|^{2}}$	(by Cauchy-Schwarz)

	$\displaystyle\\|\widetilde{R}_{i}-R_{i}\\|_{\infty}$	$\displaystyle\leq\max_{i\in[n]}\\|\widetilde{R}_{i}-R_{i}\\|_{\infty}$
		$\displaystyle=\max_{i,j\in[n]\times[\ell]}\|\widetilde{U}_{ij}-U_{ij}\|$
		$\displaystyle=\max_{j\in[\ell]}\\|\widetilde{C}_{j}-C_{j}\\|_{\infty}$
		$\displaystyle\leq\epsilon\cdot\max_{j\in[\ell]}\\|C_{j}\\|_{\infty}$
		$\displaystyle\leq\epsilon\cdot K$

	$\displaystyle(1-\epsilon)\cdot a-\epsilon^{\prime}$	$\displaystyle\leq\text{median}(\|x_{1}\|,\|x_{2}\|,\ldots,\|x_{\ell}\|)-\epsilon^{\prime}$
		$\displaystyle\leq\text{median}(\|y_{1}\|,\|y_{2}\|,\ldots,\|y_{\ell}\|)$
		$\displaystyle\leq\text{median}(\|x_{1}\|,\|x_{2}\|,\ldots,\|x_{\ell}\|)+\epsilon^{\prime}$
		$\displaystyle\leq(1+\epsilon)\cdot a+\epsilon^{\prime}$

	$\displaystyle\\|(U^{\mkern-1.5mu\mathsf{T}}b_{e})-(\widetilde{U}^{\mkern-1.5mu% \mathsf{T}}b_{e})\\|_{\infty}$	$\displaystyle=\\|(R_{u}-R_{v})-(\widetilde{R}_{u}-\widetilde{R}_{v})\\|_{\infty}$
		$\displaystyle\leq\\|R_{u}-\widetilde{R}_{u}\\|_{\infty}+\\|R_{v}-\widetilde{R}_{v% }\\|_{\infty}$
		$\displaystyle\leq 4\epsilon n^{3}K$