Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems (Q3346092)
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 3880443
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems |
scientific article; zbMATH DE number 3880443 |
Statements
Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems (English)
0 references
1984
0 references
assignment ranking techniques
0 references
traveling salesman problem
0 references
probabilistic framework
0 references
asymmetric case
0 references
0 references
0 references
0.8223966360092163
0 references
0.7939944863319397
0 references
The use of assignment ranking techniques for solving the traveling salesman problem is considered in a probabilistic framework. The principal focus of the paper is on the assumptions required for a valid mathematical analysis. For the asymmetric case, we show that the assumptions are violated when clustering of cites is present; for the symmetric problem, we show that a valid analysis can be made when 2-city subtours are eliminated. Prior probabilistic results developed by \textit{J. C. Panayiotopoulos} [Eur. J. Oper. Res. 9, 77-82 (1982; Zbl 0471.90087)] for asymmetric problems are extended to the symmetric case.
0 references