Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut

DOI10.1109/FOCS.2009.66zbMath1292.68172MaRDI QIDQ5171186

Jonah Sherman

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation algorithms (68W25)

Related Items (9)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ On the complexity of isoperimetric problems on trees ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems

This page was built for publication: Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut