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 Young

arxiv: 1704.01200 · v1 · pith:OKNQR7YHnew · submitted 2017-04-04 · 💻 cs.DS

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 Young This is my paper

classification 💻 cs.DS

keywords goemans--linialintegralityrelaxationsparsestsqrtconstantinputsleast

0 comments

read the original abstract

We prove that the integrality gap of the Goemans--Linial semidefinite programming relaxation for the Sparsest Cut Problem is $\Omega(\sqrt{\log n})$ on inputs with $n$ vertices.

This paper has not been read by Pith yet.

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

discussion (0)