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

DOI10.1002/rsa.20255zbMath1160.05303arXivcond-mat/0501760WikidataQ122925343 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

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, Algorithmic obstructions in the random number partitioning problem, 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, Replica symmetry breaking without replicas, 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