An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem

DOI10.1016/j.ejor.2017.03.061zbMath1375.90251OpenAlexW2597500097WikidataQ57659013 ScholiaQ57659013MaRDI QIDQ1683061

Markus Sinnl, Fabio Furini, Ivana Ljubić

Publication date: 6 December 2017

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2017.03.061

zbMATH Keywords

integer programmingdynamic programmingcombinatorial optimizationmaximal knapsack packingminimal knapsack cover

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (8)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ In)approximability of Maximum Minimal FVS ⋮ A lexicographic pricer for the fractional bin packing problem ⋮ (In)approximability of maximum minimal FVS ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search ⋮ On the exact separation of cover inequalities of maximum-depth

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the max min vertex cover problem
• The quadratic knapsack problem -- a survey
• Hardness of lazy packing and covering
• A minimal algorithm for the multiple-choice knapsack problem
• The lazy bureaucrat scheduling problem
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Fast algorithms for min independent dominating set
• Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems
• On lazy bureaucrat scheduling with common deadlines
• The maximum resource bin packing problem
• Upper Domination: Complexity and Approximation
• The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• The Lazy Matroid Problem
• Fourier's Method of Linear Programming and Its Dual
• ILP and CP Formulations for the Lazy Bureaucrat Problem

This page was built for publication: An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem