Phase transition and finite-size scaling for the integer partitioning problem

DOI10.1002/rsa.10004zbMath1014.05009OpenAlexW2149255574WikidataQ56112581 ScholiaQ56112581MaRDI QIDQ2772921

Christian Borgs, Boris G. Pittel, Jennifer T. Chayes

Publication date: 5 July 2003

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10004

zbMATH Keywords

phase transitionfinite-size scaling

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (10)

\(N\)-dimensional Blotto game with heterogeneous battlefield values ⋮ Local energy statistics in disordered systems: a proof of the local REM conjecture ⋮ Local energy statistics in spin glasses ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Replica symmetry breaking without replicas ⋮ Slow convergence in bootstrap percolation ⋮ Another look at the phenomenon of phase transition ⋮ 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

Cites Work

• Unnamed Item
• On sums of subsets of a set of integers
• Solving dense subset-sum problems by using analytical number theory
• The scaling window of the 2-SAT transition
• Random-energy model: An exactly solvable model of disordered systems
• Component behavior near the critical point of the random graph process
• Succinct Certificates for Almost All Subset Sum Problems
• Probabilistic analysis of the number partitioning problem
• Exponentially small bounds on the expected optimum of the partition and subset sum problems
• Phase Transition in the Number Partitioning Problem
• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• Sharp threshold and scaling window for the integer partitioning problem
• Determining computational complexity from characteristic ‘phase transitions’
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Phase transition and finite-size scaling for the integer partitioning problem