The Art Gallery Guardian

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 2014-12-13.
Tags: .