Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
From MaRDI portal
Publication:5415541
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
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