Phase transition and finite-size scaling for the integer partitioning problem
Considered is the problem of partitioning \(n\) randomly chosen integers between 1 and \(M\) into two subsets such that the discrepancy, the absolute value of the difference of their sums, is minimized. A partition is called perfect if the optimum discrepancy is 0 or 1. It is proved that there exists a perfect partition with probability 1 or 0 according to whether \(2-\log(M)/n\) has a limit less than 1 or larger than 1 as \(M\) and \(n\) tend to infinity. This result is strengthened to establish the existence of a scaling window. Furthermore, detailed information is given on the distribution of the numbers of perfect and optimum partitions. Distributional estimates of the discrepancy are also given.
- Bounds on Multiprocessing Timing Anomalies
- Component behavior near the critical point of the random graph process
- Determining computational complexity from characteristic ``phase transitions
- Exponentially small bounds on the expected optimum of the partition and subset sum problems
- scientific article; zbMATH DE number 48363 (Why is no real title available?)
- On sums of subsets of a set of integers
- Phase Transition in the Number Partitioning Problem
- Probabilistic analysis of the number partitioning problem
- Random-energy model: an exactly solvable model of disordered systems
- Sharp threshold and scaling window for the integer partitioning problem
- Solving dense subset-sum problems by using analytical number theory
- Succinct Certificates for Almost All Subset Sum Problems
- The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
- The scaling window of the 2-SAT transition
- \(N\)-dimensional Blotto game with heterogeneous battlefield values
- Replica symmetry breaking without replicas
- Instance space of the number partitioning problem
- Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
- Proof of the local REM conjecture for number partitioning. I: Constant energy scales
- Proof of the local REM conjecture for number partitioning. II. Growing energy scales
- Probabilistic analysis of optimum partitioning
- Exponentially small bounds on the expected optimum of the partition and subset sum problems
- Phase diagram for the constrained integer partitioning problem
- Sharp threshold and scaling window for the integer partitioning problem
- Another look at the phenomenon of phase transition
- LATIN 2004: Theoretical Informatics
- Algorithmic obstructions in the random number partitioning problem
- Partially ordered sets corresponding to the partition problem
- Hardness and algorithms for several new optimization problems on the weighted massively parallel computation model
- Phase transition and finite-size scaling in the vertex-cover problem
- Local energy statistics in disordered systems: a proof of the local REM conjecture
- Local energy statistics in spin glasses
- Slow convergence in bootstrap percolation
This page was built for publication: Phase transition and finite-size scaling for the integer partitioning problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2772921)
