A physicist's approach to number partitioning

DOI10.1016/S0304-3975(01)00153-0zbMath0983.68076arXivcond-mat/0009230WikidataQ59649943 ScholiaQ59649943MaRDI QIDQ5958802

No author found.

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionheuristic algorithmsstatistical mechanicsNP-completenumber partitioningrandom cost problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (18)

The Power of Optimization Over Randomization in Designing Experiments Involving Small Samples ⋮ Local energy statistics in disordered systems: a proof of the local REM conjecture ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Ordinal Maximin Share Approximation for Goods ⋮ Partitions, Diophantine equations, and control systems ⋮ Finding well-balanced pairs of edge-disjoint trees in edge-weighted graphs ⋮ OptimalA PrioriBalance in the Design of Controlled Experiments ⋮ Correspondence principle as equivalence of categories ⋮ Is computational complexity a barrier to manipulation? ⋮ Another look at the phenomenon of phase transition ⋮ Induction: From Kolmogorov and Solomonoff to De Finetti and Back to Kolmogorov ⋮ Funnels in energy landscapes ⋮ Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble ⋮ Statistical mechanics methods and phase transitions in optimization problems ⋮ Complexity of learning in artificial neural networks ⋮ Loop quantum gravity: a demystified view ⋮ Extreme value statistics and traveling fronts: Various applications ⋮ A \(p\)-spin interaction Ashkin-Teller spin-glass model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• A complete anytime algorithm for number partitioning
• Easily searched encodings for number partitioning
• Random-energy model: An exactly solvable model of disordered systems
• Probabilistic analysis of optimum partitioning
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• 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
• Determining computational complexity from characteristic ‘phase transitions’

This page was built for publication: A physicist's approach to number partitioning