ND21 M INIMUM B -B ALANCED C UT

     
• I NSTANCE : Graph , a vertex-weight function , an edge-cost function , and a rational b , .
• S OLUTION : A cut C , i.e., a subset , such that
  
  where w(V') denotes the sum of the weights of the vertices in V' .
• M EASURE : The weight of the cut, i.e.,
  
  where .

• Bad News: Not approximable within for any [ 60 ].
• Comment: Also called Minimum b -Edge Separator .     There is a polynomial algorithm that finds a b -balanced cut within an factor of the optimal -balanced cut for [ 319 ]. Approximable within 2 for planar graphs for if the vertex weights are polynomially bounded [ 125 ].     Not approximable within for graphs of maximum degree 3 [ 60 ]. The unweighted problem admits a PTAS if every vertex has degree for [ 24 ]. Minimum k -Multiway Separator , the variation in which the removal of the cut edges partitions the graph into at most k parts, where the sum of the vertex weights in each part is at most , is approximable within [ 98 ].