Integrality gaps for sparsest cut and minimum linear arrangement problems

DOI10.1145/1132516.1132594zbMath1301.05332OpenAlexW2036322374MaRDI QIDQ2931416

Rishi Saket, Nikhil R. Devanur, Subhash A. Khot, Nisheeth K. Vishnoi

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

\(\ell ^2_2\) spreading metrics for vertex ordering problems, Vertical perimeter versus horizontal perimeter, Data locality and replica aware virtual cluster embeddings, Mean isoperimetry with control on outliers: exact and approximation algorithms, Mathematics of computation through the lens of linear equations and lattices, \(d\)-dimensional arrangement revisited, Comparison of Metric Spectral Gaps, Unnamed Item, Convex Relaxations and Integrality Gaps, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, On Khot’s unique games conjecture, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁