Sashi Novitasari, Takashi Fukuda, et al.
INTERSPEECH 2025
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
Giuseppe Romano, Aakrati Jain, et al.
ECTC 2025
Charles Chiang, Majid Sarrafzadeh, et al.
IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications
Conference paper
A platform for massive agent-based simulation and its evaluation
Gaku Yamamoto, Hideki Tai, et al.
AAMAS 2008