×

How long can a Euclidean traveling salesman tour be? (English) Zbl 0682.05041

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

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
PDFBibTeX XMLCite
Full Text: DOI