Karloff, Howard J. How long can a Euclidean traveling salesman tour be? (English) Zbl 0682.05041 SIAM J. Discrete Math. 2, No. 1, 91-99 (1989). Let \(t_ N\) denote the maximum length of a shortest traveling salesman tour through N points of the unit square, distances being Euclidean. The authors improve an upper bound for \(t_ N\) of \(\sqrt{2N}+7/4\) standing for 25 years, which was derived for the Manhattan metric, reducing it to \(\alpha \sqrt{N}+11,\) where \(\alpha <0.984\sqrt{2}.\) As a consequence bounds for the shortest minimal spanning tree and minimum weight perfect matching on N points in the unit square are improved. Reviewer: F.Plastria Cited in 21 Documents MSC: 05C38 Paths and cycles 90B05 Inventory, storage, reservoirs 05C45 Eulerian and Hamiltonian graphs 51M05 Euclidean geometries (general) and generalizations 68R10 Graph theory (including graph drawing) in computer science Keywords:Euclidean distance; minimum spanning tree; traveling salesman; perfect matching PDFBibTeX XMLCite \textit{H. J. Karloff}, SIAM J. Discrete Math. 2, No. 1, 91--99 (1989; Zbl 0682.05041) Full Text: DOI