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

DOI10.1002/RSA.20255MaRDI QIDQ3619613zbMATH OpenOpenAlexWikidataFDO

Authors S. Mertens, Chandra Nair, 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/0501760

zbMATH Keywords

antiferromagnetic Ising spin glasscombinatorial optimizationenergy of a spin configurations corresponds to weight differenceNPPnumber partition problemPoisson convergencerandom energy modelREMspin 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)

Abstract: The number partitioning problem is a classic problem of combinatorial optimization in which a set of $n$ numbers is partitioned into two subsets such that the sum of the numbers in one subset is as close as possible to the sum of the numbers in the other set. When the $n$ numbers are i.i.d. variables drawn from some distribution, the partitioning problem turns out to be equivalent to a mean-field antiferromagnetic Ising spin glass. In the spin glass representation, it is natural to define energies -- corresponding to the costs of the partitions, and overlaps -- corresponding to the correlations between partitions. Although the energy levels of this model are {em a priori} highly correlated, a surprising recent conjecture asserts that the energy spectrum of number partitioning is locally that of a random energy model (REM): the spacings between nearby energy levels are uncorrelated. In other words, the properly scaled energies converge to a Poisson process. The conjecture also asserts that the corresponding spin configurations are uncorrelated, indicating vanishing overlaps in the spin glass representation. In this paper, we prove these two claims, collectively known as the local REM conjecture.

Recommendations

• Proof of the local REM conjecture for number partitioning. II. Growing energy scales
• Number partitioning as a random energy model
• Probabilistic analysis of the number partitioning problem
• Local energy statistics in disordered systems: a proof of the local REM conjecture
• Instance space of the number partitioning problem

Cites work

• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• scientific article; zbMATH DE number 52589 (Why is no real title available?)
• Local energy statistics in disordered systems: a proof of the local REM conjecture
• Number partitioning as a random energy model
• Phase transition and finite-size scaling for the integer partitioning problem
• Phase Transition in the Number Partitioning Problem
• Poisson convergence in the restricted k‐partitioning problem
• Probabilistic analysis of the number partitioning problem
• Proof of the local REM conjecture for number partitioning. II. Growing energy scales
• Random-energy model: an exactly solvable model of disordered systems
• Statistical mechanics methods and phase transitions in optimization problems
• Statistical mechanics of an NP-complete problem: subset sum

Cited in

(9)

• Distribution of levels in high-dimensional random landscapes
• Replica symmetry breaking without replicas
• Number partitioning as a random energy model
• A new REM conjecture
• Proof of the local REM conjecture for number partitioning. II. Growing energy scales
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3619613)