TSP, Max TSP and Supnick
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.
For all x\leq x', y\leq y', f:\R^2\to \R is called Supnick if it has the following properties:
- Monge: f(x,y)+f(x',y')\leq 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(n\log n) algorithm to solve the TSP problem if the distance matrix is Supnick (Supnick, 1957).
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)}) ]
-
is minimized when \pi = (1~3~5~7~\ldots~8~6~4~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 (Burkard et al., 1998).