Efficiently solvable special cases of bottleneck travelling salesman problems (Q1179263): Difference between revisions

A special case of the bottleneck travelling salesman problem is investigated. For distance matrices that are circulant matrices, it is shown that the problem can be solved in \(O(n \log n)\) time in contrast with the sum version of the problem for which this is still an open question. Sufficient conditions are then derived under which the optimal solution is a pyramidal tour. Some, but not all of these, are analogues of the same conditions for the sum version of the problem. Finally, the problem can be solved in \(O(n \log n)\) time for cost matrices \(c_{i,j}=a_ ib_ j\) where \(a_ 1\leq a_ 2\cdots\) and \(b_ 1\geq b_ 2\cdots\). The solution is not always a pyramidal tour, in distinction with the sum version where this is always the case.