A generalization of the convex-hull-and-line traveling salesman problem (Q1281349)

Summary: Two instances of the traveling salesman problem, on the same node set \(\{1,2,\dots, n\}\) but with different cost matrices \(C\) and \(C'\), are equivalent iff there exist \(\{a_i, b_i: i=1,\dots,n\}\) such that for any \(1\leq i\), \(j\leq n\), \(i\neq j\), \(C'(i,j)= C(i,j)+ a_i+ b_j\). One of the well-solved special cases of the traveling salesman problem (TSP) is the convex-hull-and-line TSP. We extend the solution scheme for this class of TSP given by \textit{V. G. Deineko}, \textit{R. van Dal} and \textit{G. Rote} [Inf. Processing Lett. 51, 141-148 (1994; Zbl 0806.90121)] to a more general class which is closed with respect to the above equivalence relation. The cost matrix in our general class is a certain composition of Kalmanson matrices. This gives a new, non-trivial solvable case of TSP.