STATISTICAL-MECHANICS OF THE KNAPSACK-PROBLEM

Authors
KORUTCHEVA E OPPER M LOPEZ B
Citation
E. Korutcheva et al., STATISTICAL-MECHANICS OF THE KNAPSACK-PROBLEM, Journal of physics. A, mathematical and general, 27(18), 1994, pp. 120000645-120000650
Citations number
12
Categorie Soggetti
Physics
Journal title
Journal of physics. A, mathematical and general → ACNP
ISSN journal
03054470
Volume
27
Issue
18
Year of publication
1994
Pages
120000645 - 120000650
Database
ISI
SICI code
0305-4470(1994)27:18<120000645:SOTK>2.0.ZU;2-Y
Abstract
The knapsack problem is an NP-complete combinatorial optimization prob lem with inequality constraints. Using the replica method of statistic al physics, we study the space of its solutions for a large problem si ze. It turns out that this problem is closely related to the theory of the binary perceptron.