  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.
