# TSP, Max TSP and Supnick

Given $f$ and $x_{1},…,x_{n}$. Find a permutation $π$ that maximizes (minimizes) $i=1∑n f(x_{π(i)},x_{π(i+1)}).$

All our index calculations are mod $n$.

Assume $f$ can be evaluated in $O(1)$ time. The TSP problem reduces to this one.

For all $x≤x_{′}$, $y≤y_{′}$, $f:R_{2}→R$ is called Supnick if it has the following properties:

- Monge: $f(x,y)+f(x_{′},y_{′})≤f(x_{′},y)+f(x,y_{′})$.
- Symmetric: $f(x,y)=f(y,x)$.

The name Supnick comes from Supnick matrix, which are symmetric Monge matrices. The following theorem implies an $O(ngn)$ algorithm to solve the TSP problem if the distance matrix is Supnick [1].

Let $x_{1}≤x_{2}≤…≤x_{n}$, $f$ is Supnick, then $i=1∑n f(x_{π(i)},x_{π(i+1)})$

is minimized when $π=(1357…8642)$.

is maximized when $π=(n2(n−2)4(n−4)…5(n−3)3(n−1)1)$.

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 [2].

# References

**Extreme hamiltonian lines**, Annals of Mathematics. Second Series. 66 (1957) 179–201.

**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.