Number Partioning as Random Energy Model

Preprint

6 July 1999

preprint
Published by arXiv in arXiv

Abstract

Number partitioning is an NP-complete problem of combinatorial optimization, which can be mapped onto an infinite range Ising spin glass with antiferromagnetic couplings. It is shown that this model is essentially equivalent to a random energy model (REM) with bounded values of the energies. The theory of extreme order statistics is applied to derive simple analytic expressions for the distribution of the ground state energy and higher excitations. In contrast to the Gaussian REM introduced by Derrida, the standard replica method fails to solve the bounded REM.

Keywords

NUMBER PARTITIONING
RANDOM ENERGY MODEL
ANTIFERROMAGNETIC
NUMBER PARTIONING
MODEL NUMBER
PARTIONING
DERRIDA
REM

All Related Versions

Version 1, 1999-07-06, ArXiv
Version 2, 1999-07-12, ArXiv
Version 3, 1999-11-10, ArXiv
Published version: Physical Review Letters, 84 (6), 1347.

This publication has 0 references indexed in Scilit: