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.

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 |