Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems

SYNOPTIC ABSTRACT

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 Panayiotopoulos for asymmetric problems are extended to the symmetric case.

Key Words and Phrases:

• Assignment ranking
• traveling salesman problem
• probabilistic analysis