Integrality gaps for sparsest cut and minimum linear arrangement problems

DOI10.1145/1132516.1132594MaRDI QIDQ2931416zbMATH OpenOpenAlexFDO

Authors Nikhil R. Devanur, Subhash Khot, Rishi Saket, 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

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

Recommendations

• Expander flows, geometric embeddings and graph partitioning
• Expander flows, geometric embeddings and graph partitioning
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• Sparsest cuts and bottlenecks in graphs

Cited in

(28)

• Vertical perimeter versus horizontal perimeter
• SDP primal-dual approximation algorithms for directed hypergraph expansion and sparsest cut with product demands
• The geometry of graphs and some of its algorithmic applications
• Lasserre integrality gaps for graph spanners and related problems
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• Data locality and replica aware virtual cluster embeddings
• \(d\)-dimensional arrangement revisited
• Mean isoperimetry with control on outliers: exact and approximation algorithms
• Convex relaxations and integrality gaps
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• Lower bounds for the minimum linear arrangement of a graph
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• On Khot’s unique games conjecture
• The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
• Approximating sparsest cut in graphs of bounded treewidth
• Cheeger-type approximation for sparsest st-cut
• The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of \(\sqrt{\log n}\)
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• Constant factor Lasserre integrality gaps for graph partitioning problems
• Comparison of metric spectral gaps
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
• Approximating non-uniform sparsest cut via generalized spectra
• Expander flows, geometric embeddings and graph partitioning
• Expander flows, geometric embeddings and graph partitioning
• Mathematics of computation through the lens of linear equations and lattices
• Sum-of-squares lower bounds for densest k-subgraph
• Theorems of KKL, Friedgut, and Talagrand via random restrictions and log-Sobolev inequality
• \(\ell ^2_2\) spreading metrics for vertex ordering problems

This page was built for publication: Integrality gaps for sparsest cut and minimum linear arrangement problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931416)