Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator

DOI10.1145/2213977.2214080MaRDI QIDQ5415541zbMATH OpenOpenAlexFDO

Authors Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1491

zbMATH Keywords

balanced graph partitioningLanczos methodmatrix exponentialspectral algorithmsuniform approximation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81) Approximation algorithms (68W25)

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 ilde{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 PSD matrices A and a given vector u, in time roughly ilde{O}(m_A), where m_A is the number of non-zero entries of A. This uses, in a non-trivial way, the result of Spielman and Teng on inverting SDD matrices in ilde{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 PSD matrices that runs in time roughly O(t_A sqrt{||A||}), where t_A is the time required for 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 ilde{O}(m/sqrt(gamma)). This latter algorithm matches the running time, but improves on the approximation guarantee of the algorithm by Andersen and Peres.

Recommendations

• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Approximating small balanced vertex separators in almost linear time
• Approximating small balanced vertex separators in almost linear time
• Integer Programming and Combinatorial Optimization
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• Approximation and parameterized algorithms for balanced connected partition problems
• Theoretical Computer Science
• Approximating LCS in Linear Time: Beating the √n Barrier
• Spectral properties of hypergraph Laplacian and approximation algorithms
• Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition

Cited in

(17)

• Spectrum-free and meshless solvers of parabolic PDEs
• Iteratively reweighted least squares and slime mold dynamics: connection and convergence
• Accelerated methods for nonconvex optimization
• Linear coupling: an ultimate unification of gradient and mirror descent
• Sublinear column-wise actions of the matrix exponential on social networks
• Graph powering and spectral robustness
• Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
• Partitioning well-clustered graphs: spectral clustering works!
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Sublinear Algorithms for Local Graph-Centrality Estimation
• Spectral sparsification via bounded-independence sampling
• Small-space spectral sparsification via bounded-independence sampling
• Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• Optimal near-optimality bounds for the Lanczos method for matrix functions
• Decremental (1+)-approximate maximum eigenvector: dynamic power method

This page was built for publication: Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415541)