A fully polynomial approximation algorithm for the 0–1 knapsack problem |
| |
| Authors: | MJ Magazine Osman Oguz |
| |
| Institution: | Department of Management Sciences, University of Waterloo, Waterloo, Ontario, Canada;Department of Operations Research and Statistics, Middle East Technical University, Ankara, Turkey |
| |
| Abstract: | A fully polynomial ?-approximation algorithm is developed for the 0–1 knapsack problem. The algorithm uses results of Lawler and Ibarra and Kim. A pseudo-polynomial dynamic programming algorithm is first suggested which solves the problem in O(nb log n) time and O(b) space. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
