Fast Algorithms for Directed Graph Partitioning Using Flows and
  Reweighted Eigenvalues
Lap Chi Lau Kam Chuen Tung Robert Wang
We consider a new semidefinite programming relaxation for directed edge
expansion, which is obtained by adding triangle inequalities to the reweighted
eigenvalue formulation. Applying the matrix multiplicative weight update method
to this relaxation, we derive almost linear-time algorithms to achieve
$O(\sqrt{\log{n}})$-approximation and Cheeger-type guarantee for directed edge
expansion, as well as an improved cut-matching game for directed graphs. This
provides a primal-dual flow-based framework to obtain the best known algorithms
for directed graph partitioning. The same approach also works for vertex
expansion and for hypergraphs, providing a simple and unified approach to
achieve the best known results for different expansion problems and different
algorithmic techniques.