Number partitioning as random energy model

Abstract

Number partitioning is a classical problem from combinatorial optimisation. In physical terms it corresponds to a long range anti-ferromagnetic Ising spin glass. It has been rigorously proven that the low lying energies of number partitioning behave like uncorrelated random variables. We claim that neighbouring energy levels are uncorrelated almost everywhere on the energy axis, and that energetically adjacent configurations are uncorrelated, too. Apparently there is no relation between geometry (configuration) and energy that could be exploited by an optimization algorithm. This ``local random energy'' picture of number partitioning is corroborated by numerical simulations and heuristic arguments.

8+2 pages, 9 figures, PDF only

References in corpus (4)

• Statistical Mechanics of an NP-complete Problem: Subset Sum
• Phase transition and landscape statistics of the number partitioning problem
• Phase Transition in Multiprocessor Scheduling
• Microscopic realizations of the Trap Model

Cited by in corpus (10)

• Extreme value problems in Random Matrix Theory and other disordered systems
• Non-ergodic extended phase of the Quantum Random Energy model
• Fast optimization algorithms and the cosmological constant
• Local energy statistics in disordered systems: a proof of the local REM conjecture
• Solution-space structure of (some) optimization problems
• Replica Symmetry Breaking without Replicas
• A simplified Parisi Ansatz II: REM universality
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
• One-in-Two-Matching Problem is NP-complete
• Local Energy Statistics in Directed Polymers