Simple but efficient approaches for the collapsing knapsack problem

DOI10.1016/S0166-218X(96)00134-5zbMath0881.90098OpenAlexW2082718338WikidataQ58826516 ScholiaQ58826516MaRDI QIDQ1364474

David Pisinger, Ulrich Pferschy, Gerhard J. Woeginger

Publication date: 4 September 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

collapsing knapsack problempseudo-polynomial solution times

Mathematics Subject Classification ID

Boolean programming (90C09)

Related Items

Integer knapsack problems with set-up weights, A new exact approach for the 0-1 collapsing knapsack problem, A heuristic approach for allocation of data to RFID tags: a data allocation knapsack problem (DAKP), An efficient algorithm for the collapsing knapsack problem, Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis, A fast algorithm for strongly correlated knapsack problems, Approximation algorithms for knapsack problems with cardinality constraints, Exact solution of a class of nonlinear knapsack problems

Uses Software

• Knapsack

Cites Work

• An exact algorithm for the 0-1 collapsing knapsack problem
• A minimal algorithm for the multiple-choice knapsack problem
• A New Algorithm for the 0-1 Knapsack Problem
• An Algorithm for Large Zero-One Knapsack Problems
• The Collapsing 0–1 Knapsack Problem