Next:
ND21 MINIMUM B-BALANCED
Up:
Cuts and Connectivity
Previous:
ND19 MINIMUM MULTI-CUT
ND20 M
INIMUM
R
ATIO
-C
UT
I
NSTANCE
: Graph
, a capacity function
, and
k
commodities, i.e.,
k
pairs
and a demand
for each pair.
S
OLUTION
: A cut, i.e., a partition of
V
into two disjoint sets
and
.
M
EASURE
: The capacity of the cut divided by the demand across the cut, i.e.,
Good News:
Approximable within
[
26
].
Comment:
Also called
Sparsest Cut
.
In the uniform-demand case the problem is in A
PX
[
233
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
, a capacity function
, and
k
commodities, i.e.,
k
pairs
and a demand
for each
pair.
and
.
[
26
].