Next: MINIMUM B-BALANCED CUT
Up: Cuts and Connectivity
Previous: MINIMUM MULTI-CUT
  Index
- INSTANCE:
Graph
,
a capacity function
,
and k
commodities, i.e., k pairs
and a demand
for each
pair.
- SOLUTION:
A cut, i.e., a partition of V into two disjoint sets
and
.
- MEASURE:
The capacity of the cut divided by the demand across the cut, i.e.,
- Good News:
Approximable within
[44].
- Comment:
Also called Sparsest Cut.
In the uniform-demand case the problem is in APX
[323].
Viggo Kann
2000-03-20