Instance space of the number partitioning problem

DOI10.1088/0305-4470/33/41/301MaRDI QIDQ2711815zbMATH OpenOpenAlexFDO

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

Publication date 26 April 2001

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

Full work available at URL https://arxiv.org/abs/cond-mat/9910525

zbMATH Keywords

integer programmingpartitioning problem

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Integer programming (90C10) Combinatorial optimization (90C27)

Abstract: Within the replica framework we study analytically the instance space of the number partitioning problem. This classic integer programming problem consists of partitioning a sequence of N positive real numbers $a_1,a_2,\mathrm{...},a_N$ (the instance) into two sets such that the absolute value of the difference of the sums of $a_j$ over the two sets is minimized. We show that there is an upper bound $alph{a}_{c}N$ to the number of perfect partitions (i.e. partitions for which that difference is zero) and characterize the statistical properties of the instances for which those partitions exist. In particular, in the case that the two sets have the same cardinality (balanced partitions) we find $alph{a}_c=1/2$. Moreover, we show that the disordered model resulting from hte instance space approach can be viewed as a model of replicators where the random interactions are given by the Hebb rule.

Recommendations

• Probabilistic analysis of the number partitioning problem
• Phase Transition in the Number Partitioning Problem
• Phase transition and finite-size scaling for the integer partitioning problem
• Phase diagram for the constrained integer partitioning problem
• Number partitioning as a random energy model

Cited in

(13)

• Correspondence principle as equivalence of categories
• An algebraic expression of the number partitioning problem
• Well-solvable instances for the partition problem
• Phase transition and finite-size scaling for the integer partitioning problem
• Number partitioning as a random energy model
• Proof of the local REM conjecture for number partitioning. I: Constant energy scales
• Universal number partition problem with divisibility
• scientific article; zbMATH DE number 2042781 (Why is no real title available?)
• Phase diagram for the constrained integer partitioning problem
• Sharp threshold and scaling window for the integer partitioning problem
• LATIN 2004: Theoretical Informatics
• A physicist's approach to number partitioning
• Algorithmic obstructions in the random number partitioning problem

This page was built for publication: Instance space of the number partitioning problem

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