A physicist's approach to number partitioning
| dc.creator | Mertens, Stephan | |
| dc.date | 2000-09-15 | |
| dc.date | 2000-11-23 | |
| dc.date.accessioned | 2026-07-07T02:38:44Z | |
| dc.date.available | 2026-07-07T02:38:44Z | |
| dc.description | The statistical physics approach to the number partioning problem, a classical NP-hard problem, is both simple and rewarding. Very basic notions and methods from statistical mechanics are enough to obtain analytical results for the phase boundary that separates the ``easy-to-solve'' from the ``hard-to-solve'' phase of the NPP as well as for the probability distributions of the optimal and sub-optimal solutions. In addition, it can be shown that solving a number partioning problem of size $N$ to some extent corresponds to locating the minimum in an unsorted list of $\bigo{2^N}$ numbers. Considering this correspondence it is not surprising that known heuristics for the partitioning problem are not significantly better than simple random search. | |
| dc.description | 35 pages, to appear in J. Theor. Comp. Science, typo corrected in eq.14 | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0009230 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0009230 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/16780 | |
| dc.subject | Condensed Matter | |
| dc.title | A physicist's approach to number partitioning | |
| dc.type | text |