The Art Gallery Guardian

TSP, Max TSP and Supnick


Given ff and x1,,xnx_1,\ldots,x_n. Find a permutation π\pi that maximizes (minimizes) i=1nf(xπ(i),xπ(i+1)). \sum_{i=1}^n f(x_{\pi(i)},x_{\pi(i+1)}).

All our index calculations are mod nn.

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


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

  1. Monge: f(x,y)+f(x,y)f(x,y)+f(x,y)f(x,y)+f(x',y')\leq f(x',y)+f(x,y').
  2. Symmetric: f(x,y)=f(y,x)f(x,y)=f(y,x).

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


Let x1x2xnx_1\leq x_2 \leq \ldots \leq x_n, ff is Supnick, then i=1nf(xπ(i),xπ(i+1)) \sum_{i=1}^n f(x_{\pi(i)},x_{\pi(i+1)})

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

  2. is maximized when π=(n 2 (n2) 4 (n4)  5 (n3) 3 (n1) 1)\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].


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