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.
