The knapsack problem with a minimum filling constraint

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

We study a knapsack problem with an additional minimum filling constraint, such that the total weight of selected items cannot be less than a given threshold. The problem has several applications in shipping, e-commerce, and transportation service procurement. When the threshold equals the knapsack capacity, even finding a feasible solution to the problem is NP-hard. Therefore, we consider the case when the ratio α of threshold to capacity is less than 1. For this case, we develop an approximation scheme that returns a feasible solution with a total profit not less than (1 - ε) times the total profit of an optimal solution for any ε > 0, and with a running time polynomial in the number of items, 1/ε, and 1/(1-α).
Original languageEnglish
Pages (from-to)56-63
Number of pages8
JournalNaval Research Logistics
Volume60
Issue number1
DOIs
Publication statusPublished - 1 Feb 2013

Keywords

  • approximation scheme
  • knapsack problem
  • minimum filling constraint
  • polynomial time

ASJC Scopus subject areas

  • Ocean Engineering
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this