Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach
Omar Kettani and Faical Ramdani. Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach. International Journal of Applied Information Systems 12(11):26-30, February 2018. URL, DOI BibTeX
@article{10.5120/ijais2018451742, author = "Omar Kettani and Faical Ramdani", title = "Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach", journal = "International Journal of Applied Information Systems", issue_date = "February 2018", volume = 12, number = 11, month = "Feb", year = 2018, issn = "2249-0868", pages = "26-30", url = "http://www.ijais.org/archives/volume12/number11/1023-2018451742", doi = "10.5120/ijais2018451742", publisher = "Foundation of Computer Science (FCS), NY, USA", address = "New York, USA" }
Abstract
In the present paper, a dynamic programming algorithm based on nonnegative least-squares approach is proposed to tackle the NP-hard knapsack feasibility problem. Some examples are presented to show the effectiveness of the proposed approach and a Matlab code implementation is provided in the appendix.
Reference
- R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds, Plenum, New York, 1972, pp. 85–103.
- O. L. Mangasarian, Knapsack Feasibility as an Absolute Value Equation Solvable by Successive Linear Programming Data Mining Institute Technical Report 08-03, September 2008. Optimization Letters 3(2) March 2009, 161-170
- H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.
- https://www.mathworks.com/
Keywords
Knapsack feasibility problem, NP-hard, nonnegative least-squares, dynamic programming