On Random Symmetric Travelling Salesman Problems

DOI10.1287/MOOR.1040.0105MaRDI QIDQ5704203zbMATH OpenOpenAlexWikidataFDO

Authors Alan Frieze

Publication date 11 November 2005

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.1040.0105

zbMATH Keywords

travelling salesman, probabilistic analysis

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Random tours in the traveling salesman problem: Analysis and application
• On the stochastic complexity of the asymmetric traveling salesman problem
• The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
• On patching algorithms for random asymmetric travelling salesman problems
• On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients
• The travelling salesman problem on a randomly diluted lattice
• Further results on the probabilistic traveling salesman problem
• Symmetric travelling salesman problem. Some new algorithmic possibilities
• scientific article; zbMATH DE number 747044

Cited in

(22)

• On patching algorithms for random asymmetric travelling salesman problems
• Computing the variance of tour costs over the solution space of the TSP in polynomial time
• A cutting plane method for risk-constrained traveling salesman problem with random arc costs
• Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
• On the longest path of a randomly weighted tournament
• Global optima results for the Kauffman \(NK\) model
• New global optima results for the Kauffman \(NK\) model: Handling dependency
• Probabilistic analysis of bipartite traveling salesman problems
• The blind passenger and the assignment problem
• Traveling Salesman Problem and Statistical Physics
• On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients
• Replica symmetry of the minimum matching
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• On constant-weight TSP-tours
• Probabilistic analysis of an approximation algorithm for the m-peripatetic salesman problem on random instances unbounded from above
• The traveling salesman problem: the spectral radius and the length of an optimal tour
• On the number of \(k\)-cycles in the assignment problem for random matrices
• Maximal Steiner trees in the stochastic mean-field model of distance
• Probabilistic analysis of optimization problems on sparse random shortest path metrics
• The mean field traveling salesman and related problems
• Random minimum spanning tree and dense graph limits
• Solving a random asymmetric TSP exactly in quasi-polynomial time w.h.p.

This page was built for publication: On Random Symmetric Travelling Salesman Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5704203)