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 di for each
pair.
- SOLUTION:
A cut, i.e., a partition of V into two disjoint sets V1 and V2.
- MEASURE:
The capacity of the cut divided by the demand across the cut, i.e.,
- Good News:
Approximable within
[41].
- Comment:
Also called Sparsest Cut.
In the uniform-demand case the problem is in APX
[306].
Viggo Kann
1999-04-22