On a quadratic programming problem involving distances in trees.

Let $$T$$ be a tree and let $$D$$ be the distance matrix of the tree. The problem of finding the maximum of $$x'Dx$$ subject to $$x$$ being a nonnegative vector with sum one occurs in many different contexts. These include some classical work on the transfinite diameter of a finite metric space, equilibrium points of symmetric bimatrix games and maximizing weighted average distance in graphs. We show that the problem can be converted into a strictly convex quadratic programming problem and hence it can be solved in polynomial time. [ABSTRACT FROM AUTHOR]