Charles Chiang, Majid Sarrafzadeh, et al.
IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications
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
Khalid Abdulla, Andrew Wirth, et al.
ICIAfS 2014
Conference paper
Learning Reduced Order Dynamics via Geometric Representations
Imran Nasim, Melanie Weber
SCML 2024
Conference paper
Program equivalence and context-free grammars
Barry K. Rosen
SWAT 1972