TSP, Max TSP and Supnick

Problem1

Given $f$ and $x_{1}, \dots, x_{n}$ . Find a permutation $π$ that maximizes (minimizes) $i = 1 \sum 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.

Definition2Supnick

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 lo g n)$ algorithm to solve the TSP problem if the distance matrix is Supnick [1].

Theorem3Supnick’s

Let $x_{1} \leq x_{2} \leq \dots \leq x_{n}$ , $f$ is Supnick, then $i = 1 \sum n f (x_{π (i)}, x_{π (i + 1)})$

is minimized when $π = (1357 \dots 8642)$ .
is maximized when $π = (n 2 (n - 2) 4 (n - 4) \dots 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]

RainerE. Burkard, E. Çela, G. Rote, GerhardJ. 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: Algorithm.