Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
Paper
A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
Abstract
The general knapsack problem is known to be NP-complete. In this paper a very special knapsack problem ia studied, namely, one with only two variables. A polynomial-time algorithm is presented and analyzed. However, it remains an open problem that for any fixed n > 2, the knapsack problem with n variables can be solved in polynomial time. © 1976, ACM. All rights reserved.
Related
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Vicki L Hanson, Edward H Lichtenstein
Cognitive Psychology