Integrality Gaps for Sparsest Cut

A quick comment about the sparsest cut integrality gaps we saw last time, and the connection to the dual. (BTW, the notes for Lec 27 are up, thanks Varun!)

In Lecture 27, the arguments for the gaps went thus: at least $k$ of the demands need to travel through $p$ edges in the network, hence sending $\tau$ fraction of each unit demand uses $\tau \cdot k\cdot p$ volume. And since we dealt with unit capacities, there was only $m$ volume in the network, hence the maximum concurrent flow is at most $m/\left(pk\right)$. For the 5-node example, $p=2$, $k=4$ and $m=6$; for the expander, $k=\Omega \left(n^2\right)$, $p=\Omega \left(\log n\right)$, and $m=O\left(n\right)$.

But suppose we are more sophisticated:

1. Suppose we assign lengths $d_e$ to each edge $e$, so that the shortest path according to these edge lengths from $i$ to $j$ is now $d_{ij}$. Think of each of the edges $(i,j)$ as pipes with capacity $C_{ij}$ and length $d_{ij}$.
   
   
2. Now if the pair $ij$ sends $\tau D_{ij}$ flow, each unit of flow must travel $d_{ij}$ distance. Hence the total volume used by this pair is $\tau D_{ij}\cdot d_{ij}$. And the total volume used is $\sum _{ij}\tau \cdot D_{ij}\cdot d_{ij}$.
   
   
3. But the total volume in the network is now $\sum _{(i,j)\in E}{C}_{ij}{d}_{ij}$.

Hence, the maximum concurrent flow ${\tau }^{*}$ is at most $\sum _{(i,j)\in E}{C}_{ij}{d}_{ij}$ divided by $\sum _{ij}\tau \cdot D_{ij}\cdot d_{ij}$. Moreover, this is true for any setting of the edge lengths $d_e$. Hence, $\tau$ is at most the minimum of $(C.d)/(D.d)$ over all metrics $d$, or in other words, $\tau \le {\lambda }^{*}$!

What we have just proved is weak LP-duality for the case of sparsest cut. The fact that ${\tau }^{*}$ equals ${\lambda }^{*}$ is given by strong duality.