A probabilistic analysis of the switching algorithm for the Euclidean TSP

DOI10.1007/BF01587089zbMath0675.90086MaRDI QIDQ1122505

Walter Kern

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

simulated annealingprobabilistic analysisEuclidean Traveling Salesmank-switching algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ Analysis of random restart and iterated improvement for global optimization with application to the traveling salesman problem ⋮ Mechanisms for local search

Cites Work

• Unnamed Item
• Unnamed Item
• On the number of iterations of local improvement algorithms
• Probabilistic exchange algorithms and Euclidean traveling salesman problems
• The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
• Some Examples of Difficult Traveling Salesman Problems
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: A probabilistic analysis of the switching algorithm for the Euclidean TSP