Probabilistic analysis of the number partitioning problem

DOI10.1088/0305-4470/31/15/007MaRDI QIDQ4254273zbMATH OpenOpenAlexFDO

Authors F. F. Ferreira, José F. Fontanari

Publication date 15 February 2000

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/adap-org/9801002

zbMATH Keywords

antiferromagnetic Ising modelfraction of metastable statesnumber partitioning problem

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Miscellaneous applications of number theory (11Z05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: Given a sequence of $N$ positive real numbers $a_1,a_2,\mathrm{...},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}$.

Recommendations

• Probabilistic analysis for random integer partitions
• scientific article; zbMATH DE number 1472145
• Probabilistic analysis of optimum partitioning
• Asymptotic analysis of random partitions
• Randomized methods for the number partitioning problem
• Integer partitions probability distributions
• scientific article; zbMATH DE number 176070
• Analysis of some new partition statistics
• scientific article; zbMATH DE number 52589

Cited in

(19)

• Heuristics and exact methods for number partitioning
• Phase transitions of subset sum and Shannon's limit in source coding
• Hard combinatorial problems and minor embeddings on lattice graphs
• Randomized methods for the number partitioning problem
• Instance space of the number partitioning problem
• Phase transition and finite-size scaling for the integer partitioning problem
• Number partitioning as a random energy model
• Two metaheuristic approaches for solving multidimensional two-way number partitioning problem
• Proof of the local REM conjecture for number partitioning. I: Constant energy scales
• Probabilistic analysis of optimum partitioning
• Phase Transition in the Number Partitioning Problem
• Microscopic realizations of the trap model
• Distribution of the number of fitness maxima in Fisher’s geometric model
• Number partitioning on a quantum computer
• A physicist's approach to number partitioning
• Algorithmic obstructions in the random number partitioning problem
• On some similarity of finite sets (and what we can say today about certain old problem)
• Integer linear programming model for multidimensional two-way number partitioning problem
• Evolutionary accessibility of random and structured fitness landscapes

This page was built for publication: Probabilistic analysis of the number partitioning problem

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