Approximations for the isoperimetric and spectral profile of graphs and related parameters

DOI10.1145/1806689.1806776zbMath1293.05214OpenAlexW2098350988MaRDI QIDQ2875190

David Steurer, Prasad Raghavendra, Prasad Tetali

Publication date: 13 August 2014

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

Full work available at URL: https://doi.org/10.1145/1806689.1806776

zbMATH Keywords

semidefinite programmingapproximation algorithmsparse principal component analysisgraph expansionsmall-set expansionspectral profile

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Semidefinite programming (90C22) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Approximation algorithms (68W25)

Related Items (5)

Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Total Variation Isoperimetric Profiles ⋮ Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions

This page was built for publication: Approximations for the isoperimetric and spectral profile of graphs and related parameters