On approximating the incremental knapsack problem

DOI10.1016/j.dam.2019.02.016zbMath1423.90218arXiv1801.04801OpenAlexW2963897343WikidataQ128316774 ScholiaQ128316774MaRDI QIDQ2422736

Rosario Scatamacchia, Ulrich Pferschy, Frederico Della Croce

Publication date: 20 June 2019

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

Full work available at URL: https://arxiv.org/abs/1801.04801

zbMATH Keywords

linear programmingapproximation schemeincremental knapsack problem

Mathematics Subject Classification ID

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

Related Items

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ Approximation schemes for multiperiod binary knapsack problems

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The online knapsack problem with incremental capacity
• Approximation schemes for the parametric knapsack problem
• Approximation algorithms for knapsack problems with cardinality constraints
• New exact approaches and approximation results for the penalized knapsack problem
• Approximation results for the incremental knapsack problem
• An exact approach for the 0-1 knapsack problem with setups
• Exact approaches for the knapsack problem with setups
• A PTAS for the time-invariant incremental knapsack problem
• Approximating the 3-period incremental knapsack problem
• A new exact approach for the 0-1 collapsing knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
• Technical Note—The Multiperiod Knapsack Problem
• Approximate Algorithms for the 0/1 Knapsack Problem
• Beating ratio 0.5 for weighted oblivious matching problems
• An ILP-based Proof System for the Crossing Number Problem
• Improved dynamic programming and approximation results for the knapsack problem with setups
• An Incremental Model for Combinatorial Maximization Problems
• Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation