Probabilistic analysis of solving the assignment problem for the traveling salesman problem

DOI10.1016/0377-2217(82)90014-5zbMath0471.90087OpenAlexW1968577698MaRDI QIDQ1158107

J.-C. Panayiotopoulos

Publication date: 1982

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(82)90014-5

zbMATH Keywords

probabilistic analysisoptimal solutionsassignment problemrandom databranch-and-bound methodsasymmetric traveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05)

Related Items

On the stochastic complexity of the asymmetric traveling salesman problem, Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems, Heuristic methods and applications: A categorized survey, A useful transform of standard input data for a classical NP-complete problem

Cites Work

• Unnamed Item
• Unnamed Item
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• A statistical approach to the tsp
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• Branch-and-Bound Methods: A Survey
• An Algorithm for the Traveling Salesman Problem
• The Traveling Salesman Problem: A Survey
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost