Universal conditions for algebraic Travelling Salesman Problems to be efficiently solvable

The authors 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, the authors investigate conditions which guarantee that an optimal tour is pyramidal and can therefore be determined in O(n²) time. Furthermore, they discuss TSPs with Brownian as well as those with left-upper-triangular cost matrices.