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.
|