Proof of the local REM conjecture for number partitioning. II. Growing energy scales
DOI10.1002/rsa.20256zbMath1160.05304arXivcond-mat/0508600WikidataQ123231272 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
NPP; combinatorial optimization; random energy model; REM; Poisson convergence; antiferromagnetic Ising spin glass; energy of a spin configurations corresponds to weight difference; number partiotion problem; spin configurations correspond to partitions; sum of numbers in subset
05A17: Combinatorial aspects of partitions of integers
60K35: Interacting random processes; statistical mechanics type models; percolation theory
82B44: Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics
Related Items
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