A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems
Jack A.A. van der Veen · SIAM Journal on Discrete Mathematics · 1994
An instance of the symmetric traveling salesman problem (STSP) is pyramidally solvable if there is a shortest tour that is pyramidal. A pyramidal tour is a Hamiltonian tour that consists of two parts; according to the labeling of the vertices in the first part the vertices are visited in increasing order and in the second part in decreasing order. It is well known that a shortest pyramidal tour can be found in $\mathcal{O}( n^2 )$ time. In this paper it is shown that the STSP restricted to the class of distance matrices \[ \mathbb{D}_{{\text{NEW}}} = \left\{ D = ( d [ i, j ] )\bigg| \begin{matrix} d\left[ {i,j} \right] = d\left[ {j,i} \right]\quad{\text{for all }}i\,{\text{and }}j\\ d\left[ {i,j} \right] + d\left[ {j + 1,k} \right] \leq d \left[ {i,k} \right] + d\left[ {j,j + 1} \right]\quad {\text{for all }}i < j < j + 1 < k \end{matrix} \right\}\] is pyramidally solvable. Furthermore, it is shown that $\mathbb{D}_{{\text{NEW}}} ot\subset \mathbb{D}_{{\text{DEMI}}} $, i.e., that $\mathbb{D}_{{\text{NEW}}} $ is not contained in the class of symmetric Demidenko matrices $\mathbb{D}_{{\text{DEMI}}} $ that was, until now, the most general class of pyramidally solvable STSPs. It is also shown that $\mathbb{D}_{{\text{DEMI}}} ot\subset \mathbb{D}_{{\text{NEW}}} $.