×

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

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

Citations:

Zbl 0562.00014