  


Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)Time Spectral Algorithm for Balanced Separator
Lorenzo Orecchia(orecchiamit.edu) Abstract: We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter \gamma, either finds an \Omega(b)balanced cut of conductance O(\sqrt{\gamma}) in G, or outputs a certificate that all bbalanced cuts in G have conductance at least \gamma, and runs in time \tilde{O}(m). This settles the question of designing asymptotically optimal spectral algorithms for balanced separator. Our algorithm relies on a variant of the heat kernel random walk and requires, as a subroutine, an algorithm to compute \exp(L)v where L is the Laplacian of a graph related to G and v is a vector. Algorithms for computing the matrixexponentialvector product efficiently comprise our next set of results. Our main result here is a new algorithm which computes a good approximation to \exp(A)v for a class of symmetric positive semidefinite (PSD) matrices A and a given vector u, in time roughly \tilde{O}(m_A), where m_A is the number of nonzero entries of A. This uses, in a nontrivial way, the breakthrough result of Spielman and Teng on inverting symmetric and diagonallydominant matrices in \tilde{O}(m_A) time. Finally, we prove e^{x} can be uniformly approximated up to a small additive error, in a nonnegative interval [a,b] with a polynomial of degree roughly \sqrt{ba}. While this result is of independent interest in approximation theory, we show that, via the Lanczos method from numerical analysis, it yields a simple algorithm to compute \exp(A)v for symmetric PSD matrices that runs in time roughly O(t_A \sqrt{A}), where t_A is time required for the computation of the vector Aw for given vector w. As an application, we obtain a simple and practical algorithm, with output conductance O(\sqrt{\gamma}), for balanced separator that runs in time \tilde{O}(m/\sqrt{\gamma}). This latter algorithm matches the running time, but improves on the approximation guarantee of the EvolvingSetsbased algorithm by Andersen and Peres for balanced separator. Keywords: Spectral Algorithms, Balanced Graph Partitioning, Matrix Exponential, Lanczos Method, Uniform Approximation. Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 11/06/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  