Computing the variance of tour costs over the solution space of the TSP in polynomial time

DOI10.1007/s10589-012-9472-0zbMath1262.90154MaRDI QIDQ1935572

Jenny Edwards, Paul J. Sutcliffe, Andrew Solomon

Publication date: 18 February 2013

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-012-9472-0

zbMATH Keywords

moments; variance; Hamiltonian cycle; traveling salesman problem; statistics; stochastic; probabilistic; landscapes

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

Optimal TSP tour length estimation using standard deviation as a predictor

Uses Software

• TSPLIB
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• The mean field traveling salesman and related problems
• The traveling salesman. Computational solutions for RSP applications
• Probability theory of classical Euclidean optimization problems
• The theory of elementary landscapes
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• The traveling salesman problem and its variations
• A sharp deviation inequality for the stochastic traveling salesman problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• TSPLIB—A Traveling Salesman Problem Library
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Algorithms on Strings, Trees and Sequences
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• On Random Symmetric Travelling Salesman Problems
• Local search structure in the symmetric travelling salesperson problem under a general class of rearrangement neighborhoods
• Random tours in the traveling salesman problem: Analysis and application