On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions

The purpose of this paper is to investigate a family of large-scale linear programming relaxations of the so-called Graph Partitioning Problem. Based on the concept of maximum cost ratio subset, a characterization of optimal solutions to some problems in the family is given. From this, a purely combinatorial solution algorithm is obtained for solving the corresponding problems. The resulting bounds may be used, for example, to validate approximate (heuristic) solutions or to implement branch and bound procedures.