The graph bisection minimization problem

A method of determining a lower bound for the graph bisection minimization problem is described. The bound is valid for weighted graphs with edge and node weights. The approach is based on Lagrangian relaxation and was previously used for determining an upper bound on the independence number of a graph. The determination of the lower bound is done by solving a quadratic programming problem. A characterization of the solutions of this problem is proved which allows to approximate the optimal solution of the graph bisection minimization problem. Some computational experiments are reported.