# TSP, Max TSP and Supnick

Problem1

Given $f$ and $x_1,\ldots,x_n$. Find a permutation $\pi$ that maximizes (minimizes) $\sum_{i=1}^n f(x_{\pi(i)},x_{\pi(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.

Definition2Supnick

For all $x\leq x'$, $y\leq y'$, $f:\R^2\to \R$ is called Supnick if it has the following properties:

1. Monge: $f(x,y)+f(x',y')\leq f(x',y)+f(x,y')$.
2. 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(n\log n)$ algorithm to solve the TSP problem if the distance matrix is Supnick [1].

Theorem3Supnick’s

Let $x_1\leq x_2 \leq \ldots \leq x_n$, $f$ is Supnick, then $\sum_{i=1}^n f(x_{\pi(i)},x_{\pi(i+1)})$

1. is minimized when $\pi = (1~3~5~7~\ldots~8~6~4~2)$.

2. is maximized when $\pi = (n ~ 2 ~ (n-2) ~ 4 ~ (n-4) ~\ldots~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

[1] F. Supnick, Extreme hamiltonian lines, Annals of Mathematics. Second Series. 66 (1957) 179–201.

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

Posted by Chao Xu on .
Tags: Algorithm.