Title: Near-linear time algorithms for Balanced Separator by simulating random walks
Speaker: Sushant Sachdeva, Princeton University
Date: Wednesday, March 13, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The goal of the Balanced Separator problem is to cut a graph into two roughly equal parts, while minimizing the number of edges cut. It is a fundamental problem, both in theory and practice. Given the massive size of several graphs of interest today (e.g. the web graph), we would like near-linear time algorithms for this problem. In this talk, we present the first such algorithm with an approximation guarantee that's optimal for spectral algorithms.
We first show how to reduce the question of finding a good balanced cut to simulating poly-logarithmic number of continuous-time random walks, using techniques from semidefinite programming, and matrix exponential updates.
Next, we give a near-linear time algorithm to approximately simulate the required random walks (equivalent to approximating the matrix exponential e^(-tL), where L is the graph Laplacian). We show how to achieve such an approximation using rational functions, techniques from numerical linear algebra, and the near-linear time Laplacian system solver by Spielman and Teng.
This is joint work with Lorenzo Orecchia and Nisheeth K. Vishnoi.