Mattias Ohlsson
Professor
A study of the mean field approach to knapsack problems
Författare
Summary, in English
The mean field theory approach to knapsack problems is extended to multiple knapsacks and generalized assignment problems with Potts mean field equations governing the dynamics. Numerical tests against 'state of the art' conventional algorithms shows good performance for the mean field approach. The inherently parallelism of the mean field equations makes them suitable for direct implementations in microchips. It is demonstrated numerically that the performance is essentially not affected when only a limited number of bits is used in the mean field equations. Also, a hybrid algorithm with linear programming and mean field components is showed to further improve the performance for the difficult homogeneous N x M knapsack problem.
Avdelning/ar
- Beräkningsbiologi och biologisk fysik - Har omorganiserats
Publiceringsår
1997-03
Språk
Engelska
Sidor
263-271
Publikation/Tidskrift/Serie
Neural Networks
Volym
10
Issue
2
Dokumenttyp
Artikel i tidskrift
Förlag
Elsevier
Ämne
- Other Computer and Information Science
Nyckelord
- finite precision
- generalized assignment problems
- knapsack problems
- mean field theory
- neural networks
Status
Published
ISBN/ISSN/Övrigt
- ISSN: 0893-6080