Routing under Balance

Alina Ene, Gary Miller, Jakub Pachocki +1

We introduce the notion of balance for directed graphs: a weighted directed graph is $\alpha$-balanced if for every cut $S\subseteq V$, the total weight of edges going from $S$ to $V\s…