Universal conditions for algebraic travelling salesman problems to be efficiently solvable
Rainer E. Burkard, Jack A.A. van der Veen · Optimization · 1991
We consider Travelling Salesman Problems (TSPs) where the cost of a tour is an algebraic composition of the cost coefficients that are elements of a totally ordered, commutative semigroup. Conditions for the cost matrix are stated which allow to solve these problems in polynomial time. In particular, we investigate conditions which guarantee that an optimal tour is pyramidal and can therefore be determined in O(n 2) time. Furthermore, we discuss TSPs with Brownian as well as those with left-upper-triangular cost matrices.