| Abstract: | 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. |
