scientific article; zbMATH DE number 3932819

From MaRDI portal
Publication:3707785





[For the entire collection see Zbl 0562.00014.] This chapter is an excellent self-contained paper on probabilistic analysis of two versions of the travelling salesman problem (TSP). In the first problem, the locations of cities are drawn independently from the uniform distribution over the d-dimensional unit cube and distances between locations are Euclidean. The authors show that the cost of an optimal tour will be close to \(C_ dn^{(d-1)/d}\) (where \(C_ d\) is a constant), when n, the number of cities is large. Cellular dissection algorithms, which find optimal tours in each of many small rectangles and then are patched together to find tours in the unit square, are described in detail. It is shown that this efficient algorithm yields near optimal solutions and has the same asymptotic behavior of the length of the optimal tour. In the other model, elements of the distance matrix are drawn independently from the uniform distribution over the 2-dimensional unit sequence. In this model neither symmetry nor the triangle inequality is assumed. An approximation algorithm for the TSP is presented based on the assignment problem. It is shown that this algorithm tends to give near optimal tours when the number of cities is very large. The paper is written with a section on the required probabilistic background, several exercises and some open questions.




Cited in
(54)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3707785)