Research Article
Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach
|
International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
|
| Volume 12 - Issue 11 |
| Published: Feb 2018 |
| Authors: Omar Kettani, Faical Ramdani |
10.5120/ijais2018451742
|
Omar Kettani, Faical Ramdani . Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach. International Journal of Applied Information Systems. 12, 11 (Feb 2018), 26-30. DOI=10.5120/ijais2018451742
@article{ 10.5120/ijais2018451742,
author = { Omar Kettani,Faical Ramdani },
title = { Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach },
journal = { International Journal of Applied Information Systems },
year = { 2018 },
volume = { 12 },
number = { 11 },
pages = { 26-30 },
doi = { 10.5120/ijais2018451742 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2018
%A Omar Kettani
%A Faical Ramdani
%T Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach%T
%J International Journal of Applied Information Systems
%V 12
%N 11
%P 26-30
%R 10.5120/ijais2018451742
%I Foundation of Computer Science (FCS), NY, 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.
References
- 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/
Index Terms
Keywords