Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition

Lorenzo Orecchia, Nisheeth K. Vishnoi

In this paper, we consider the following graph partitioning problem: The input is an undirected graph $G=(V,E),$ a balance parameter $b\in (0,1/2]$ and a target conductance value…