No label defined (Q3707785)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3932819
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3932819 |
Statements
1985
0 references
probabilistic analysis
0 references
travelling salesman
0 references
locations of cities
0 references
optimal tour
0 references
Cellular dissection algorithms
0 references
near optimal solutions
0 references
asymptotic behavior
0 references
approximation
0 references
assignment
0 references
0.9378331
0 references
0.9110453
0 references
0.90384674
0 references
0 references
0.8995252
0 references
[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.
0 references