Proof of the local REM conjecture for number partitioning. I: Constant energy scales

DOI10.1002/rsa.20255zbMath1160.05303arXivcond-mat/0501760OpenAlexW3083572948WikidataQ122925343 ScholiaQ122925343MaRDI QIDQ3619613

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

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/0501760

zbMATH Keywords

NPPcombinatorial optimizationrandom energy modelREMPoisson convergenceantiferromagnetic Ising spin glassenergy of a spin configurations corresponds to weight differencenumber partition 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 (7)

Local energy statistics in disordered systems: a proof of the local REM conjecture ⋮ Local energy statistics in spin glasses ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Replica symmetry breaking without replicas ⋮ 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. II. Growing energy scales

Cites Work

• Unnamed Item
• Local energy statistics in disordered systems: a proof of the local 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. II. Growing energy scales
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Probabilistic analysis of the number partitioning problem
• Phase Transition in the Number Partitioning Problem
• Statistical mechanics of an NP-complete problem: subset sum
• Poisson convergence in the restricted k‐partitioning problem
• Statistical mechanics methods and phase transitions in optimization problems

This page was built for publication: Proof of the local REM conjecture for number partitioning. I: Constant energy scales