New exact approaches and approximation results for the penalized knapsack problem

DOI10.1016/J.DAM.2017.11.023MaRDI QIDQ1634770zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ulrich Pferschy, Rosario Scatamacchia, F. 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

approximation schemesdynamic programmingexact algorithmpenalized knapsack problem

Mathematics Subject Classification ID

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

Recommendations

• An optimization algorithm for a penalized knapsack problem
• Approximation issues of fractional knapsack with penalties: a note
• Integer optimization with penalized fractional values: the knapsack case
• Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
• A new approximation algorithm for the knapsack problem

Cites work

• A Minimal Algorithm for the 0-1 Knapsack Problem
• A New Algorithm for the 0-1 Knapsack Problem
• An optimization algorithm for a penalized knapsack problem
• Approximation results for the incremental knapsack problem
• scientific article; zbMATH DE number 3687091 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Integer optimization with penalized fractional values: the knapsack case
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Two-dimensional packing problems: a survey

Cited in

(14)

• Integer optimization with penalized fractional values: the knapsack case
• The multiple multidimensional knapsack with family-split penalties
• Approximation issues of fractional knapsack with penalties: a note
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
• On approximating the incremental knapsack problem
• An optimization algorithm for a penalized knapsack problem
• A penalty algorithm for solving convex separable knapsack problems
• Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties
• The knapsack problem with forfeit sets
• A decomposition approach for multidimensional knapsacks with family‐split penalties
• One-dimensional bin packing with pattern-dependent processing time
• Lower bounds for DAG scheduling in the cloud

Describes a project that uses

Uses Software

• CPLEX
• Knapsack

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1634770)