Back to Search
Start Over
Multistage knapsack.
- Source :
-
Journal of Computer & System Sciences . Jun2022, Vol. 126, p106-118. 13p. - Publication Year :
- 2022
-
Abstract
- Many systems have to be maintained while the underlying constraints, costs and/or profits change over time. Although the state of a system may evolve during time, a non-negligible transition cost is incurred for transitioning from one state to another. In order to model such situations, we look at a recently introduced multistage model where the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) that are both (i) near optimal for each time step and (ii) as stable as possible. We propose a PTAS for the Multistage Knapsack problem. This is the first approximation scheme for a combinatorial optimization problem in the considered multistage setting, and its existence contrasts with the inapproximability results for other combinatorial optimization problems that are even polynomial-time solvable in the static case. [ABSTRACT FROM AUTHOR]
- Subjects :
- *COMBINATORIAL optimization
*KNAPSACK problems
*BACKPACKS
*APPROXIMATION algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 126
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 155363934
- Full Text :
- https://doi.org/10.1016/j.jcss.2022.01.002