Computer Science/Discrete Mathematics Seminar I

Partitioning the vertices of a graph into two (roughly) equal parts to minimize the weight of edges cut is a fundamental optimization problem, arising in diverse applications. Despite intense research, there remains a huge gap in our understanding of the approximability of these problems -- the best algorithms achieve a factor (log n)^{\Omega(1)} approximation as a function of the number n of vertices, whereas even a factor 1.1 approximation is not known to be NP-hard. We describe an approximation scheme for various graph partitioning problems such as sparsest cut, minimum bisection, and small set expansion. Specifically, we give an algorithm running in time n^{O_epsilon(r)} with approximation ratio (1+epsilon)/min(1,lambda_r), where lambda_r is the r'th smallest eigenvalue of the normalized graph Laplacian matrix. This perhaps indicates why even showing very weak hardness for these problems has been elusive, since the reduction must produce hard instances with slowly growing spectra. Our algorithm is based on a rounding procedure for semidefinite programming relaxations from a strong class called the Lasserre hierarchy. The analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix. Our methods apply more broadly to optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes other notorious problems such as Unique Games, which we again show to be easy when the normalized Laplacian doesn't have too many small eigenvalues. Joint work with Ali Kemal Sinop.