ND23 M INIMUM Q UOTIENT C UT

     
• I NSTANCE : Graph , a vertex-weight function , and an edge-cost function .
• S OLUTION : A cut C , i.e., a subset .
• M EASURE : The quotient of the cut, i.e.,
  
  where c(C) denotes the sum of the costs of the edges (u,v) such that either and or and and, for any subset , w(V') denotes the sum of the weights of the vertices in V' .

• Good News: Approximable within [ 248 ].
• Comment: Also called Minimum Flux Cut .     Admits a PTAS for planar graphs [ 286 ].     The generalization to hypergraphs, also called Minimum Net Expansion , is approximable within in the uniform vertex-weight case [ 266 ]. Other approximation algorithms for hypergraph partitioning problems are contained in [ 266 ].