Sparsest-cut and negative-type metrics
Recall that the sparsest-cut value
is defined as:
Arora-Rao-Vazirani: Key Theorem
Assume
are such that for all
it holds that
, as well as:
then
there exist
such that:
,
,
, and
and so forth until the end of proof.