Scaling and universality in continuous length combinatorial optimization

DOI10.1073/PNAS.1635191100MaRDI QIDQ5460806zbMATH OpenOpenAlexWikidataFDO

Authors David Aldous, Allon G. Percus

Publication date 19 July 2005

Published in Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1073/pnas.1635191100

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Phase Transitions in Combinatorial Optimization Problems
• Percolation–like scaling exponents for minimal paths and trees in the stochastic mean field model
• Cost distributions in large combinatorial optimisation problems
• scientific article; zbMATH DE number 4133843
• Scaling features in complex optimization problems

Cites work

• A sharp deviation inequality for the stochastic traveling salesman problem
• Broadcasting on trees and the Ising model.
• Optimization by simulated annealing
• The (2) limit in the random assignment problem
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

Cited in

(11)

• The planted matching problem: phase transitions and exact results
• Many hard examples in exact phase transitions
• Edge flows in the complete random-lengths network
• Cost distributions in large combinatorial optimisation problems
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• A stochastic complex network model
• Percolation–like scaling exponents for minimal paths and trees in the stochastic mean field model
• A survey of max-type recursive distributional equations
• The mean field traveling salesman and related problems
• Learning-based TSP-solvers tend to be overly greedy
• Near-minimal spanning trees: A scaling exponent in probability models

This page was built for publication: Scaling and universality in continuous length combinatorial optimization

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