The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of $\sqrt{\log n}$

Assaf Naor, Robert M. Young

Type: Preprint

Publication Date: 2017-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.1704.01200

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n	2017	Assaf Naor Robert M. Young
+ PDF Chat	A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+	A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+	A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+ PDF Chat	On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension	2020	Fernando Mário de Oliveira Filho Frank Vallentin
+	Merging techniques for combinatorial optimization: spectral graph theory and semidefinite programming	2009	Umesh Vazirani Alexandra Kolla
+	Merging Techniques for Combinatorial Optimization: Spectral Graph Theory and Semidefinite Programming - eScholarship	2009	Alexandra Kolla
+	Cutting planes for semidefinite relaxations based on triangle-free subgraphs	2015	Abraham Berman Mirjam Dür Naomi Shaked-Monderer Julia Witzel
+	A sub-constant improvement in approximating the positive semidefinite Grothendieck problem	2014	Roy Frostig Sida I. Wang
+ PDF Chat	Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems	2014	Venkatesan Guruswami Ali Kemal Sinop Yuan Zhou
+	Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems	2012	Venkatesan Guruswami Ali Kemal Sinop Yuan Zhou
+	Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming	2018	Charles Carlson Alexandra Kolla Ray Li Nitya Mani Benny Sudakov Luca Trevisan
+	Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming	2018	C. W. Carlson Alexandra Kolla Ray Li Nitya Mani Benny Sudakov Luca Trevisan
+	Lower Bounds for Max-Cut via Semidefinite Programming	2020	Charles Carlson Alexandra Kolla Ray Li Nitya Mani Benny Sudakov Luca Trevisan
+	Integrality gaps for strong linear programming and semidefinite programming relaxations	2010	Konstantinos Georgiou
+	Parameterized Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth	2023	Richard Y. Zhang
+	Cheeger-type approximation for sparsest $st$-cut	2014	Robert Krauthgamer Tal Wagner
+	Cheeger-type approximation for sparsest $st$-cut	2014	Robert Krauthgamer Tal Wagner
+	Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?	2013	Luca Trevisan
+ PDF Chat	The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem	2018	Samuel C. Gutekunst David P. Williamson

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (7)

Action	Title	Year	Authors
+	Plongements lipschitziens dans Rn	2003	Patrice Assouad
+	A Course in Metric Geometry	2001	Dmitri Burago Yuri Burago S. V. Ivanov
+	On the distribution of the fourier spectrum of Boolean functions	2002	Jean Bourgain
+ PDF Chat	Differentiating maps into<i>L</i><sup>1</sup>, and the geometry of<i>BV</i>functions	2010	Jeff Cheeger Bruce Kleiner
+	On lipschitz embedding of finite metric spaces in Hilbert space	1985	Jean Bourgain
+	Euclidean distortion and the sparsest cut	2007	Sanjeev Arora James Lee Assaf Naor
+	An Introduction to the Heisenberg Group and the Sub-Riemannian Isoperimetric Problem	2007	Luca Capogna Scott D. Pauls Donatella Danielli Jeremy T. Tyson