Next: MINIMUM B-BALANCED CUT Up: Cuts and Connectivity Previous: MINIMUM MULTI-CUT Index

### MINIMUM RATIO-CUT

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