PHASE-TRANSITION IN THE NUMBER PARTITIONING PROBLEM

Authors
MERTENS S
Citation
S. Mertens, PHASE-TRANSITION IN THE NUMBER PARTITIONING PROBLEM, Physical review letters, 81(20), 1998, pp. 4281-4284
Citations number
11
Categorie Soggetti
Physics
Journal title
Physical review letters → ACNP
ISSN journal
00319007
Volume
81
Issue
20
Year of publication
1998
Pages
4281 - 4284
Database
ISI
SICI code
0031-9007(1998)81:20<4281:PITNPP>2.0.ZU;2-Q
Abstract
Number partitioning is an NP-complete problem of combinatorial optimiz ation. A statistical mechanics analysis reveals the existence of a pha se transition that separates the easy- from the hard-to-solve instance s and that reflects the pseudopolynomiality of number partitioning. Th e phase diagram and the value of the typical ground-state energy are c alculated. [S0031-9007(98)07670-4].