The Wiener maximum quadratic assignment problem

We investigate a special case of the maximum quadratic assignment problem where one matrix is a product matrix and the other matrix is the distance matrix of a one‐dimensional point set. We show that this special case, which we call the Wiener maximum quadratic assignment problem, is NP‐hard in the ordinary sense and solvable in pseudo‐polynomial time. Our approach also yields a polynomial time solution for the following problem from chemical graph theory: find a tree that maximizes the Wiener index among all trees with a prescribed degree sequence. This settles an open problem from the literature.