Gilmore, P. C.; Lawler, E. L.; Shmoys, D. B. Well-solved special cases. (English) Zbl 0631.90081 The traveling salesman problem, a guided tour of combinatorial optimization, 87-143 (1985). [For the entire collection see Zbl 0562.00014.] The authors give an excellent survey on special travelling salesman problems which can be solved by polynomial algorithms. There are two kinds of conditions possible: algebraic conditions for the cost matrix or graph theoretic conditions on the underlying network. In particular the following problem classes are treated: the “constant” TSP yields the same objective function value for all tours. Its cost elements have the form \(c_{ij}=ai+b_ j\) for given vectors \(a=(a_ i)\) and \(b=(b_ j)\). Also “small TSP’s” with \(c_{ij}=\min \{a_ i,b_ j\}\) can be solved polynomially, whereas Sarvanov showed that the TSP with product matrices \(c_{ij}=a_ ib_ j\) is NP-hard. A proof of this famous theorem is given. Moreover, an extensive survey on the general Demidenko- conditions, the theory of pyramidal tours and subtour patching is given (inclusive proofs). Here also the Gilmore-Gomory case is treated. Moreover it is mentioned that circulants as cost-matrices allow to find polynomially an open Hamiltonian path whereas it is an open question whether the Hamiltonian tour problem is NP-hard. TSPs with graded matrices \((c_{ij}\leq c_{ij+1}\) for all i,j) are NP-hard for sum objectives, but polynomially tractible for bottleneck objectives. TSPs with upper triangular cost-matrices can be solved via assignment problems. This leads to graphtheoretic conditions: TSPs on networks with limited bound widths and on Halin graphs can be solved by efficient algorithms. Reviewer: R.E.Burkard Cited in 3 ReviewsCited in 72 Documents MSC: 90C35 Programming involving graphs or networks 90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming 68Q25 Analysis of algorithms and problem complexity 05C35 Extremal problems in graph theory Keywords:survey; travelling salesman; polynomial algorithms; pyramidal tours; subtour patching; circulants; open Hamiltonian path; limited bound widths; Halin graphs Citations:Zbl 0562.00014 PDFBibTeX XML