Probabilistic Analysis of the Number Partitioning Problem

Abstract

Given a sequence of $N$ positive real numbers $\{a_1,a_2,...,a_N\}$, the number partitioning problem consists of partitioning them into two sets such that the absolute value of the difference of the sums of $a_j$ over the two sets is minimized. In the case that the $a_j$'s are statistically independent random variables uniformly distributed in the unit interval, this NP-complete problem is equivalent to the problem of finding the ground state of an infinite-range, random anti-ferromagnetic Ising model. We employ the annealed approximation to derive analytical lower bounds to the average value of the difference for the best constrained and unconstrained partitions in the large $N$ limit. Furthermore, we calculate analytically the fraction of metastable states, i.e. states that are stable against all single spin flips, and found that it vanishes like $N^{-3/2}$.

14 pages and 5 figures

References in corpus (1)

• Statistical mechanics of the multi-constraint continuous knapsack problem

Cited by in corpus (18)

• Phase Transition in the Number Partitioning Problem
• Random Costs in Combinatorial Optimization
• A physicist's approach to number partitioning
• Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
• Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine
• Number partitioning as random energy model
• Relaxation in graph coloring and satisfiability problems
• On Minimum Violations Ranking in Paired Comparisons
• Statistical Mechanics of an NP-complete Problem: Subset Sum
• Efficient exploration of discrete energy landscapes
• Phase transition and landscape statistics of the number partitioning problem
• Number Partitioning on a Quantum Computer
• Evolutionary accessibility of random and structured fitness landscapes
• Distribution of the number of fitness maxima in Fisher's Geometric Model
• Statistical Mechanics Analysis of the Continuous Number Partitioning Problem
• Entropy-based analysis of the number partitioning problem
• Subset sum phase transitions and data compression
• Instance Space of the Number Partitioning Problem