Approximating the 3-period incremental knapsack problem

DOI10.1016/j.jda.2018.11.005zbMath1416.90041OpenAlexW2901045911WikidataQ128950914 ScholiaQ128950914MaRDI QIDQ1711662

Rosario Scatamacchia, Ulrich Pferschy, Frederico 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

linear programmingapproximation algorithmincremental knapsack problem

Mathematics Subject Classification ID

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

Related Items (3)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation schemes for the parametric 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
• A new exact approach for the 0-1 collapsing knapsack problem
• Exact and approximate algorithms for discounted \(\{0\text{-}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

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