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

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

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

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

NPP; combinatorial optimization; random energy model; REM; Poisson convergence; antiferromagnetic Ising spin glass; energy of a spin configurations corresponds to weight difference; number partition 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, Local energy statistics in disordered systems: a proof of the local 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. 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