New exact approaches and approximation results for the penalized knapsack problem

DOI10.1016/j.dam.2017.11.023zbMath1411.90292OpenAlexW2774060613WikidataQ61638284 ScholiaQ61638284MaRDI QIDQ1634770

Rosario Scatamacchia, Ulrich Pferschy, Frederico Della Croce

Publication date: 18 December 2018

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

Full work available at URL: https://doi.org/10.1016/j.dam.2017.11.023

zbMATH Keywords

dynamic programmingapproximation schemesexact algorithmpenalized knapsack problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (7)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties ⋮ On approximating the incremental knapsack problem ⋮ The knapsack problem with forfeit sets ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ A decomposition approach for multidimensional knapsacks with family‐split penalties ⋮ The multiple multidimensional knapsack with family-split penalties

Uses Software

• CPLEX
• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Integer optimization with penalized fractional values: the knapsack case
• Approximation results for the incremental knapsack problem
• Two-dimensional packing problems: a survey
• An optimization algorithm for a penalized knapsack problem
• A New Algorithm for the 0-1 Knapsack Problem
• A Minimal Algorithm for the 0-1 Knapsack Problem
• Linear Time Algorithms for Knapsack Problems with Bounded Weights

This page was built for publication: New exact approaches and approximation results for the penalized knapsack problem