CFP last date
15 May 2024
Call for Paper
June Edition
IJAIS solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 15 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Analysis of ANN Training Algorithms for Hand Geometry-Based Access Control

Kazeem B. Adedeji Apena Waliu O. Adu Michael R.
Random Articles
Reseach Article

Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach

by Omar Kettani, Faical Ramdani
journal cover thumbnail

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

Powered by PhDFocusTM