The Goemans-Linial relaxation is a semidefinite programming optimization relaxation
of sparsest cut. For uniform
sparsest cut of a graph 
on 
vertices, let 
be nonnegative capacities
on unordered pairs and assign vectors 
to the vertices.
Put 
,
the squared Euclidean distance. The relaxed
optimum is
 |
subject to 
and all triangle inequalities 
. Distinct vertices
may have zero distance. For a cut
with part 
,
taking 
on separated pairs and 0 on the other pairs is feasible, so 
, the uniform
sparsest cut optimum.
