Phase Transition in the Number Partitioning Problem
From MaRDI portal
Abstract: Number partitioning is an NP-complete problem of combinatorial optimization. A statistical mechanics analysis reveals the existence of a phase transition that separates the easy from the hard to solve instances and that reflects the pseudo-polynomiality of number partitioning. The phase diagram and the value of the typical ground state energy are calculated.
Recommendations
Cites work
Cited in
(30)- Heuristics and exact methods for number partitioning
- GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem
- Topological phase transitions in the theory of partitions of integers
- Block rearranging elements within matrix columns to minimize the variability of the row sums
- Phase transitions of subset sum and Shannon's limit in source coding
- Loop quantum gravity: a demystified view
- Hard combinatorial problems and minor embeddings on lattice graphs
- An algebraic expression of 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
- Phase transitions in integer linear problems
- Two metaheuristic approaches for solving multidimensional two-way number partitioning problem
- Proof of the local REM conjecture for number partitioning. I: Constant energy scales
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- Statistical mechanics of an NP-complete problem: subset sum
- Microscopic realizations of the trap model
- scientific article; zbMATH DE number 868179 (Why is no real title available?)
- Statistical and algebraic analysis of a family of random Boolean equations
- Number partitioning on a quantum computer
- A physicist's approach to number partitioning
- Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
- 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
- Finding maximum independent set based on multi-stage simulated quantum adiabatic evolution
- Partially ordered sets corresponding to the partition problem
- Hardness and algorithms for several new optimization problems on the weighted massively parallel computation model
- Local energy statistics in disordered systems: a proof of the local REM conjecture
- Local energy statistics in spin glasses
This page was built for publication: Phase Transition in the Number Partitioning Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4492521)
