Approximating the 3-period incremental knapsack problem

DOI10.1016/J.JDA.2018.11.005MaRDI QIDQ1711662zbMATH OpenOpenAlexWikidataFDO

Authors Ulrich Pferschy, Rosario Scatamacchia, F. Della Croce

Publication date 18 January 2019

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2018.11.005

zbMATH Keywords

approximation algorithmincremental knapsack problemlinear programming

Mathematics Subject Classification ID

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

Recommendations

• On approximating the incremental knapsack problem
• Approximation results for the incremental knapsack problem
• Approximation algorithms for the generalized incremental knapsack problem
• Approximation schemes for multiperiod binary knapsack problems
• A new approximate algorithm for the knapsack problem
• Approximation Algorithms for 3D Orthogonal Knapsack
• A new approximation algorithm for the knapsack problem
• Approximation schemes for the parametric knapsack problem
• Constant-time approximation algorithms for the knapsack problem
• An algorithm for the periodic solutions in the knapsack problem

Cites work

• A new exact approach for the 0-1 collapsing knapsack problem
• A PTAS for the time-invariant incremental knapsack problem
• An exact approach for the 0-1 knapsack problem with setups
• An ILP-based Proof System for the Crossing Number Problem
• An Incremental Model for Combinatorial Maximization Problems
• Approximation results for the incremental knapsack problem
• Approximation schemes for the parametric knapsack problem
• Beating ratio 0.5 for weighted oblivious matching problems
• Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
• Exact approaches for the knapsack problem with setups
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Improved dynamic programming and approximation results for the knapsack problem with setups
• Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation

Cited in

(6)

• Approximation results for the incremental knapsack problem
• A PTAS for the time-invariant incremental knapsack problem
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• On approximating the incremental knapsack problem
• Approximation algorithms for the generalized incremental knapsack problem
• Technical Note—An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem

This page was built for publication: Approximating the 3-period incremental knapsack problem

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