Optimal grouping of researchers into departments

The authors deal with the class of those quadratic semi-assignment problems-in maximization form-in which the coefficients of the quadratic terms are non-negative and those of the linear terms are arbitrary. For a given problem in this class, they introduce a linear programming relaxation, and show that this optimal value coincides with both the optimum of the roof-dual and the optimum of the Lagrangian dual. Furthermore, the authors prove that the relative duality gap never exceedes one half. The linear programming relaxation is seen to be a network flow problem with side constraints; dwelling on this special structure, they develop a combinatorial solution algorithm.