Back to Search
Start Over
Approximation algorithms for the generalized incremental knapsack problem.
- Source :
-
Mathematical Programming . Mar2023, Vol. 198 Issue 1, p27-83. 57p. - Publication Year :
- 2023
-
Abstract
- We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative weight, and T time periods with non-decreasing capacities W 1 ≤ ⋯ ≤ W T . When item i is inserted at time t, we gain a profit of p it ; however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the time-dependent capacity constraints, with the objective of maximizing our total profit. Interestingly, this setting subsumes as special cases a number of recently-studied incremental knapsack problems, all known to be strongly NP-hard. Our first contribution comes in the form of a polynomial-time (1 2 - ϵ) -approximation for the generalized incremental knapsack problem. This result is based on a reformulation as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys–Tardos algorithm for the generalized assignment problem. Combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we turn our algorithm into a quasi-polynomial time approximation scheme (QPTAS). Hence, under widely believed complexity assumptions, this finding rules out the possibility that generalized incremental knapsack is APX-hard. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 198
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 162012623
- Full Text :
- https://doi.org/10.1007/s10107-021-01755-7