Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper

-

November Edition 2021
International Journal of Applied Information Systems solicits high quality original research papers for the November 2021 Edition of the journal. The last date of research paper submission is October 15, 2021.

Solving Knapsack Feasibility Problem via Nonnegative Least-Squares Approach

Omar Kettani, Faical Ramdani in Applied Mathematics

International Journal of Applied Information Systems
Year of Publication: 2018
Publisher: Foundation of Computer Science (FCS), NY, USA
Series: Volume 12 Number 11
Authors:Omar Kettani, Faical Ramdani
10.5120/ijais2018451742
Download full text

  1. 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

  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/

Keywords

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