Scaling and universality in continuous length combinatorial optimization

DOI10.1073/pnas.1635191100zbMath1063.90041OpenAlexW2109111228WikidataQ24673245 ScholiaQ24673245MaRDI QIDQ5460806

David J. 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

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

Related Items (8)

Many hard examples in exact phase transitions ⋮ The mean field traveling salesman and related problems ⋮ A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ A survey of max-type recursive distributional equations ⋮ A stochastic complex network model ⋮ Edge flows in the complete random-lengths network ⋮ Near-minimal spanning trees: A scaling exponent in probability models ⋮ The planted matching problem: phase transitions and exact results

Cites Work

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

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