Theorem 1 .

Super-Greedy++ is a $(1-\epsilon)$ -apx to DSS after $T\geq O\left(\frac{\Delta\log n}{\lambda^{*}\epsilon^{2}}\right)$ iterations.

Lemma 2 .

SG is just OPMWU with $\alpha=e^{\epsilon}$ and at every iteration $t$ ,

•

The load $\ell_{v}^{t}$ in SG is $Qy^{t}$ in OPMWU. Thus $w^{t}=e^{\eta\ell_{v}^{t}}$
•

Each $\pi$ in SG corresponds to $\sigma$ in OPMWU.

Lemma 3 .

If $\pi$ is a peeling order of SG++ and $v\prec u$ according to $\pi$ , then $\ell_{u}\leq\ell_{v}+\Delta$ .

Lemma 4 .

At every iteration $t$ , there is an approximate vector $\tilde{w}^{t}$ such that

1.

$w^{t}\leq\tilde{w}^{t}\leq e^{\epsilon}w^{t}$
2.

$\pi^{t}$ is decreasing in $\tilde{w}^{t}$

Lemma 5 .

For any feasible solution $x$ to the covering LP, there is a set of threshold vertices with density $\frac{\lambda^{*}}{\|x\|_{1}}$ .

Lemma 6 .

At some iteration $t\leq T_{\hat{w}ever}$ , the vector $\textrm{normalized}(w^{t})$ is a feasible $\beta$ -apx solution to the covering LP.

Lemma 7 .

At every iteration when $\textrm{normalized}(w^{t})$ is not a $\beta$ -apx, we also have that

w^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}<\alpha\cdot\|w\|_{1}\cdot\lambda^% {*}

Theorem 1 .

Super-Greedy++ is a $(1-\epsilon)$ -apx to DSS after $T\geq O\left(\frac{\Delta\log n}{\lambda^{*}\epsilon^{2}}\right)$ iterations.

Proof.

By Lemma 2 , SG++ is an instantiation of OPMWU with $\alpha=e^{\epsilon}$ . Let $\pi^{t}$ be the peeling orders in SG++ in each iteration. Let $\{\ell^{t}\}$ be the loads and $\{w^{t}\}$ be the weights of that OPMWU.

By Lemma 6 , there is an iteration where $x^{t}=\textrm{normalized}(w^{t})$ is a $(1+\epsilon)\alpha$ -apx solution to densest subgraph. Let $t$ be that iteration.

By Lemma 4 , there is a vector $\tilde{w}^{t}$ with $w^{t}\leq\tilde{w}^{t}\leq e^{\epsilon}w^{t}$ , such that $\pi^{t}$ is decreasing in $\tilde{w}^{t}$ . Define $\tilde{x}^{t}=\textrm{normalized}(\tilde{w}^{t})$ .

$\displaystyle\hat{f}(\tilde{x})$	$\displaystyle=\min_{\sigma}\tilde{x}^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\sigma}$	(by definition of f)
	$\displaystyle=\tilde{x}^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}$	(since $\pi$ is decreasing in $\tilde{x}$ )
	$\displaystyle\geq e^{-\epsilon}x^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}$	(by Lemma 8 )
	$\displaystyle\geq e^{-\epsilon}\hat{f}(x)$	(by definition of f)
	$\displaystyle\geq(1-O(\epsilon))\lambda^{*}$	(since x is almost optimal)

∎

Lemma 2 .

SG is just OPMWU with $\alpha=e^{\epsilon}$ and at every iteration $t$ ,

•

The load $\ell_{v}^{t}$ in SG is $Qy^{t}$ in OPMWU. Thus $w^{t}=e^{\eta\ell_{v}^{t}}$
•

Each $\pi$ in SG corresponds to $\sigma$ in OPMWU.

Proof.

It is true at $t=0$ when $\ell=0^{V}$ and $w=1^{V}$ . In every iteration of MWU, there is a minimization problem:

Find the $\sigma$ that minimizes $w^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\sigma}$ .

We show that $\pi$ from SG++ achieves a $e^{\epsilon}$ approximation to this minimum value. Once we show this, the weights exponentiating $\ell_{v}$ is obvious since

Qy^{t}=\sum_{t}Q\mathbbm{1}_{\sigma^{t}}=\sum_{t}\ell^{t}

where the last inequality is because $Q\mathbbm{1}_{\sigma}$ is the peeled degrees of all vertices when peeling according to $\sigma$ .

To prove the claim, let $\gamma$ be the minimizer of $w^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\sigma}$ . We have that

$\displaystyle w^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}$	$\displaystyle\leq\tilde{w}^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}$	( Lemma 4 and positivity of $Q\mathbbm{1}_{\pi}$ )
	$\displaystyle\leq\tilde{w}^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\gamma}$
	$\displaystyle\leq e^{\epsilon}w^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\gamma}$	( Lemma 4 and positivity of $Q\mathbbm{1}_{\gamma}$ )

∎

Lemma 3 .

If $\pi$ is a peeling order of SG++ and $v\prec u$ according to $\pi$ , then $\ell_{u}\leq\ell_{v}+\Delta$ .

Proof.

Suppose $\ell_{u}>\ell_{v}+\Delta$ . Then

\ell_{v}+q(v,\pi)\leq\ell_{v}+\Delta<\ell_{u}\leq\ell_{u}+q(u,\pi)

which would mean that $v$ would be peeled before $u$ , a contradiction. ∎

Lemma 4 .

At every iteration $t$ , there is an approximate vector $\tilde{w}^{t}$ such that

1.

$w^{t}\leq\tilde{w}^{t}\leq e^{\epsilon}w^{t}$
2.

$\pi^{t}$ is decreasing in $\tilde{w}^{t}$

Proof.

Let $\gamma$ be the ordering that is decreasing in $\ell_{v}$ . Then it is also decreasing in $w_{v}$ since $w_{v}=\exp(\eta\ell_{v})$ . Define $\tilde{w}_{v}=\max_{u\succ v}w_{u}$ . Then blah blah

$\displaystyle\tilde{w}_{v}$	$\displaystyle=w_{u}=\exp(\eta\ell_{u})$
	$\displaystyle\leq\exp(\eta\ell_{v})\cdot\exp(\eta\Delta)$	(by Lemma 3 )
	$\displaystyle\leq w_{v}\cdot\exp(\epsilon)$

This sets $\eta=\epsilon/\Delta$ . ∎

Lemma 5 .

For any feasible solution $x$ to the covering LP, there is a set of threshold vertices with density $\frac{\lambda^{*}}{\|x\|_{1}}$ .

Lemma 6 .

At some iteration $t\leq T_{\hat{w}ever}$ , the vector $\textrm{normalized}(w^{t})$ is a feasible $\beta$ -apx solution to the covering LP.

Proof.

∎

Lemma 7 .

At every iteration when $\textrm{normalized}(w^{t})$ is not a $\beta$ -apx, we also have that

w^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}<\alpha\cdot\|w\|_{1}\cdot\lambda^% {*}

Proof.

This is true because

	$\displaystyle w^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}$	$\displaystyle=\\|w\\|_{1}\cdot x^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}$
		$\displaystyle\leq\alpha\cdot\\|w\\|_{1}\cdot\min_{\sigma}x^{\mkern-1.5mu\mathsf{% T}}Q\mathbbm{1}_{\sigma}$
		$\displaystyle<\frac{\alpha}{\beta}\cdot\\|w\\|_{1}\cdot\lambda^{*}$

∎

	$\displaystyle w^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}$	$\displaystyle=\\|w\\|_{1}\cdot x^{\mkern-1.5mu\mathsf{T}}Q\mathbbm{1}_{\pi}$
		$\displaystyle\leq\alpha\cdot\\|w\\|_{1}\cdot\min_{\sigma}x^{\mkern-1.5mu\mathsf{% T}}Q\mathbbm{1}_{\sigma}$
		$\displaystyle<\frac{\alpha}{\beta}\cdot\\|w\\|_{1}\cdot\lambda^{*}$

Theorem 1 .

Lemma 2 .

Lemma 3 .

Lemma 4 .

Lemma 5 .

Lemma 6 .

Lemma 7 .

Lemma 8 .

Theorem 1 .

Proof.

Lemma 2 .

Proof.

Lemma 3 .

Proof.

Lemma 4 .

Proof.

Lemma 5 .

Lemma 6 .

Proof.

Lemma 7 .

Proof.

Lemma 8 .