A multiple penalty function method for solving max-bisection problems (Q2489432)

The authors study the max-bisection problem, defined as the problem of dividing the vertices of a given graph into two sets of equal cardinality such that the induced cut is of maximum edge weight. In the first section they introduce the above problem using binary decision variables, while in the second section a novel nonlinear continuous reformulation of the max-bisection problem is presented. The last two sections of this very interesting article concentrate on algorithmic aspects of the formulation such as multiple penalty functions and the results of numerical experimentation.