John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
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.
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Gosia Lazuka, Andreea Simona Anghel, et al.
SC 2024
Ran Iwamoto, Kyoko Ohara
ICLC 2023
Bing Zhang, Mikio Takeuchi, et al.
NAACL 2025