- INSTANCE:
Graph
,
a vertex-weight function
,
and an
edge-cost function
.
- SOLUTION:
A cut
*C*, i.e., a subset . - MEASURE:
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 [345].*Comment:*Also called*Minimum Flux Cut*. Admits a PTAS for planar graphs [395]. The generalization to hypergraphs, also called*Minimum Net Expansion*, is approximable within in the uniform vertex-weight case [368]. Other approximation algorithms for hypergraph partitioning problems are contained in [368].