Combinatorial optimization problems in trace form

Some important combinatorial optimization problems may be presented in a matrix form in which an optimal permutation has to be determined. A reformulation of these problems gives an expression in matrix trace form, which leads to an equivalent norm maximization problem. This allows one to obtain bounds that are related to the eigenvalues of the underlying matrices. In particular the Hoffman-Wielandt inequality and various eigenvalue spread reduction schemes yield improvements over previous bounding techniques.