Routing under balance

We introduce the notion of balance for directed graphs: a weighted directed graph is α-balanced if for every cut S ⊆ V , the total weight of edges going from S to V ∖ S is within factor α of the total weight of edges going from V ∖ S to S . Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with α = 1) and residual graphs of (1+є)-approximate undirected maximum flows (with α= O (1/є)).

Authors

• Alina Ene
• Gary L. Miller
• Jakub Pachocki
• Aaron Sidford

Keywords

• Balanced Directed Graphs
• Directed Graphs
• Gradient Descent
• Graph Clustering
• Maximum Flow
• Oblivious Rout- ing