A PTAS for the time-invariant incremental knapsack problem

DOI10.1007/978-3-319-96151-4_14zbMATH Open1404.90112arXiv1701.07299OpenAlexW2883223373MaRDI QIDQ1661876FDOQ1661876

Igor Malinović, Yuri Faenza

Publication date: 17 August 2018

Abstract: The Time-Invariant Incremental Knapsack problem (IIK) is a generalization of Maximum Knapsack to a discrete multi-period setting. At each time, capacity increases and items can be added, but not removed from the knapsack. The goal is to maximize the sum of profits over all times. IIK models various applications including specific financial markets and governmental decision processes. IIK is strongly NP-hard and there has been work on giving approximation algorithms for some special cases. In this paper, we settle the complexity of IIK by designing a PTAS based on rounding a disjuncive formulation, and provide several extensions of the technique.

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (5)

• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Approximating the 3-period incremental knapsack problem
• Approximation schemes for multiperiod binary knapsack problems
• On approximating the incremental knapsack problem
• Approximation algorithms for the generalized incremental knapsack problem

   Recommendations

• On approximating the incremental knapsack problem 👍 👎
• Title not available (Why is that?) 👍 👎
• Approximation algorithms for the generalized incremental knapsack problem 👍 👎
• Approximation results for the incremental knapsack problem 👍 👎
• An iterative dynamic programming approach for the temporal knapsack problem 👍 👎
• Constant-Time Approximation Algorithms for the Knapsack Problem 👍 👎
• An FPTAS for the parametric knapsack problem 👍 👎
• Algorithms for randomized time-varying knapsack problems 👍 👎
• The Temporal Knapsack Problem and Its Solution 👍 👎
• Approximating the 3-period incremental knapsack problem 👍 👎

This page was built for publication: A PTAS for the time-invariant incremental knapsack problem

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