TSP, Max TSP and Supnick
Given and . Find a permutation that maximizes (minimizes)
All our index calculations are mod .
Assume can be evaluated in time. The TSP problem reduces to this one.
For all , , is called Supnick if it has the following properties:
- Monge: .
- Symmetric: .
Let , is Supnick, then
is minimized when .
is maximized when .
Supnick matrices appears at many places. For example, maximize the area of a radar chart and find a permutation maximize sum of adjacent distance.
It is a special case of a even larger class of problem that has the above permutation as solution: Quadratic assignment problem where the matrices are monotone antimonge and benevolent symmetric toeplitz matrix .
 F. Supnick, Extreme hamiltonian lines, Annals of Mathematics. Second Series. 66 (1957) 179–201.
 R. Burkard, E. Çela, G. Rote, G. Woeginger, The quadratic assignment problem with a monotone anti-monge and a symmetric toeplitz matrix: Easy and hard cases, Mathematical Programming. 82 (1998) 125–158 10.1007/BF01585868.