The mean field traveling salesman and related problems

DOI10.1007/s11511-010-0046-7zbMath1231.90370OpenAlexW2001032631MaRDI QIDQ617874

Johan Wästlund

Publication date: 14 January 2011

Published in: Acta Mathematica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11511-010-0046-7

zbMATH Keywords

combinatoricsgraph theoryweighted graphstraveling salesman problemspanning treesoptimal matching problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Distance in graphs (05C12) Optimality conditions for problems involving randomness (49K45)

Related Items (18)

THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS ⋮ Average optimal cost for the Euclidean TSP in one dimension ⋮ Computing the variance of tour costs over the solution space of the TSP in polynomial time ⋮ Replica symmetry of the minimum matching ⋮ Scaling window for mean-field percolation of averages ⋮ Diameter of the Stochastic Mean-Field Model of Distance ⋮ Maximal Steiner Trees in the Stochastic Mean-Field Model of Distance ⋮ Random-link matching problems on random regular graphs ⋮ Belief propagation for optimal edge cover in the random complete graph ⋮ The Blind Passenger and the Assignment Problem ⋮ On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph ⋮ Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs ⋮ On the Nearest-Neighbor Algorithm for the Mean-Field Traveling Salesman Problem ⋮ Endogeny for the logistic recursive distributional equation ⋮ The random fractional matching problem ⋮ Successive shortest paths in complete graphs with random edge weights ⋮ The planted matching problem: phase transitions and exact results ⋮ A general method for lower bounds on fluctuations of random variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of max-type recursive distributional equations
• On the value of a random minimum spanning tree problem
• Asymptotics in the random assignment problem
• The stochastic traveling salesman problem: finite size scaling and the cavity prediction
• A proof of Parisi's conjecture on the random assignment problem
• Nature's way of optimizing
• Broken replica symmetry bounds in the mean field spin glass model
• Concentration of measure and isoperimetric inequalities in product spaces
• The Parisi formula
• The ?(2) limit in the random assignment problem
• Counting independent sets up to the tree threshold
• On the Expected Value of a Random Assignment Problem
• On the expected value of the minimum assignment
• The weight of the shortest path tree
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Information, Physics, and Computation
• Constructive bounds and exact expectations for the random assignment problem
• Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
• LU decomposition of matrices with augmented dense constraints
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Percolation–like scaling exponents for minimal paths and trees in the stochastic mean field model
• Scaling and universality in continuous length combinatorial optimization
• On Random Symmetric Travelling Salesman Problems
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

This page was built for publication: The mean field traveling salesman and related problems