MINIMUM RATIO-CUT

• INSTANCE: Graph $G=\left(V,E\right)$, a capacity function $c : E \rightarrow N$, and k commodities, i.e., k pairs $(s_i,t_i) \in V^2$ and a demand $d_i$ for each pair.

• SOLUTION: A cut, i.e., a partition of V into two disjoint sets $V_1$ and $V_2$.

• MEASURE: The capacity of the cut divided by the demand across the cut, i.e.,

  
  

  $$\sum_{v_1\in V_1, v_2\in V_2 \atop (v_1,v_2) \in E}c(v_1,v_2)/ \sum_{i:\vert\{s_i,t_i\} \cap V_1\vert=1}d_i.$$
  
  

  
  

• Good News: Approximable within $O(\log k)$ [44].
• Comment: Also called Sparsest Cut. In the uniform-demand case the problem is in APX [323].