CFP last date
16 December 2024
Reseach Article

Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach

by Omar Kettani, Faical Ramdani
International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 12 - Number 11
Year of Publication: 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 },
issue_date = { Feb 2018 },
volume = { 12 },
number = { 11 },
month = { Feb },
year = { 2018 },
issn = { 2249-0868 },
pages = { 26-30 },
numpages = {9},
url = { https://www.ijais.org/archives/volume12/number11/1023-2018451742/ },
doi = { 10.5120/ijais2018451742 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T19:08:48.834941+05:30
%A Omar Kettani
%A Faical Ramdani
%T Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 12
%N 11
%P 26-30
%D 2018
%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
  1. 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.
  2. 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
  3. H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.
  4. https://www.mathworks.com/
Index Terms

Computer Science
Information Sciences

Keywords

Knapsack feasibility problem NP-hard nonnegative least-squares dynamic programming