×

A generalization of the convex-hull-and-line traveling salesman problem. (English) Zbl 0918.90131

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 V. G. Deineko, R. van Dal and 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.

MSC:

90C35 Programming involving graphs or networks

Citations:

Zbl 0806.90121
PDFBibTeX XMLCite
Full Text: DOI EuDML