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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

OptimalA PrioriBalance in the Design of Controlled Experiments, Algorithmic obstructions in the random number partitioning problem, 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, Distribution of levels in high-dimensional random landscapes, 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