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

DOI10.1145/2213977.2214080zbMath1286.05099arXiv1111.1491OpenAlexW2089703809MaRDI QIDQ5415541

Sushant Sachdeva, Lorenzo Orecchia, 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

Lanczos methoduniform approximationmatrix exponentialspectral algorithmsbalanced graph partitioning

Mathematics Subject Classification ID

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

Related Items (11)

Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Iteratively reweighted least squares and slime mold dynamics: connection and convergence ⋮ Accelerated Methods for NonConvex Optimization ⋮ Computing heat kernel PageRank and a local clustering algorithm ⋮ Sublinear Algorithms for Local Graph-Centrality Estimation ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Spectrum-free and meshless solvers of parabolic PDEs ⋮ Sublinear Column-wise Actions of the Matrix Exponential on Social Networks ⋮ Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent ⋮ Graph Powering and Spectral Robustness

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