Optimization Online


An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing

Fabio Furini(fabio.furini***at***dauphine.fr)
Ivana Ljubic(ivana.ljubic***at***essec.edu)
Markus Sinnl(markus.sinnl***at***univie.ac.at)

Abstract: Given a set of n items with profits and weights and a knapsack capacity C, we study the problem of finding a maximal knapsack packing that minimizes the profit of selected items. We propose for the first time an effective dynamic programming (DP) algorithm which has O(nC) time complexity and O(n+C) space complexity. We demonstrate the equivalence between this problem and the problem of finding a minimal knapsack cover that maximizes the profit of selected items. In an extensive computational study on a large and diverse set of benchmark instances, we demonstrate that the new DP algorithm outperforms the use of a state-of-the-art commercial mixed integer programming (MIP) solver applied to the two best-performing MIP models from the literature.


Category 1: Combinatorial Optimization

Category 2: Integer Programming

Category 3: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 09/20/2016
Entry Accepted: 09/21/2016
Entry Last Modified: 09/20/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society