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
      0 references
      0 references
      1984
      0 references
      assignment ranking techniques
      0 references
      traveling salesman problem
      0 references
      probabilistic framework
      0 references
      asymmetric case
      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

      Identifiers