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