Optimization Online


Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

Lorenzo Orecchia(orecchia***at***mit.edu)
Sushant Sachdeva(sachdeva***at***cs.princeton.edu)
Nisheeth K. Vishnoi(nisheeth.vishnoi***at***gmail.com)

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 b-balanced 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 matrix-exponential-vector 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 non-zero entries of A. This uses, in a non-trivial way, the breakthrough result of Spielman and Teng on inverting symmetric and diagonally-dominant matrices in \tilde{O}(m_A) time. Finally, we prove e^{-x} can be uniformly approximated up to a small additive error, in a non-negative interval [a,b] with a polynomial of degree roughly \sqrt{b-a}. 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 Evolving-Sets-based 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 (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 11/06/2011
Entry Accepted: 11/07/2011
Entry Last Modified: 11/06/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society