PhD Seminar • Algorithms and Complexity • Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues

Please note: This PhD seminar will take place in DC 3317 and online.

Robert Wang, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Lap Chi Lau

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 an O(sqrt(logn))- 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.

To join this PhD seminar in person, please go to DC 3317. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/6574898503.