Proof of the local REM conjecture for number partitioning. II. Growing energy scales

DOI10.1002/rsa.20256zbMath1160.05304arXivcond-mat/0508600OpenAlexW4246048305WikidataQ123231272 ScholiaQ123231272MaRDI QIDQ3619614

Chandra Nair, Stephan Mertens, Christian Borgs, Jennifer T. Chayes

Publication date: 8 April 2009

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/0508600

zbMATH Keywords

NPPcombinatorial optimizationrandom energy modelREMPoisson convergenceantiferromagnetic Ising spin glassenergy of a spin configurations corresponds to weight differencenumber partiotion problemspin configurations correspond to partitionssum of numbers in subset

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Related Items

Local energy statistics in disordered systems: a proof of the local REM conjecture ⋮ A tomography of the GREM: Beyond the REM conjecture ⋮ Local energy statistics in spin glasses ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Distribution of levels in high-dimensional random landscapes ⋮ OptimalA PrioriBalance in the Design of Controlled Experiments ⋮ Proof of the local REM conjecture for number partitioning. I: Constant energy scales

Cites Work

• Local energy statistics in disordered systems: a proof of the local REM conjecture
• A tomography of the GREM: Beyond the REM conjecture
• Phase transition and finite-size scaling for the integer partitioning problem
• Number partitioning as a random energy model
• Random-energy model: An exactly solvable model of disordered systems
• Proof of the local REM conjecture for number partitioning. I: Constant energy scales
• Exponentially small bounds on the expected optimum of the partition and subset sum problems
• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• Saddlepoint Approximations in Statistics