License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.22
URN: urn:nbn:de:0030-drops-109664
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10966/
Go to the corresponding LIPIcs Volume Portal

Bampis, Evripidis ; Escoffier, Bruno ; Teiller, Alexandre

Multistage Knapsack

pdf-format:
LIPIcs-MFCS-2019-22.pdf (0.5 MB)

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 incured for transitioning from one state to another. In order to model such situations, Gupta et al. (ICALP 2014) and Eisenstat et al. (ICALP 2014) introduced a 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 simultaneously (i) have good quality on the time steps and (ii) as stable as possible. We focus on the multistage version of the Knapsack problem where we are given a time horizon t=1,2,...,T, and a sequence of knapsack instances I_1,I_2,...,I_T, one for each time step, defined on a set of n objects. In every time step t we have to choose a feasible knapsack S_t of I_t, which gives a knapsack profit. To measure the stability/similarity of two consecutive solutions S_t and S_{t+1}, we identify the objects for which the decision, to be picked or not, remains the same in S_t and S_{t+1}, giving a transition profit. We are asked to produce a sequence of solutions S_1,S_2,...,S_T so that the total knapsack profit plus the overall transition profit is maximized.
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 (e.g.multistage Spanning Tree, or multistage Bipartite Perfect Matching). Then, we prove that there is no FPTAS for the problem even in the case where T=2, unless P=NP. Furthermore, we give a pseudopolynomial time algorithm for the case where the number of steps is bounded by a fixed constant and we show that otherwise the problem remains NP-hard even in the case where all the weights, profits and capacities are 0 or 1.

BibTeX - Entry

@InProceedings{bampis_et_al:LIPIcs:2019:10966,
  author =	{Evripidis Bampis and Bruno Escoffier and Alexandre Teiller},
  title =	{{Multistage Knapsack}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10966},
  URN =		{urn:nbn:de:0030-drops-109664},
  doi =		{10.4230/LIPIcs.MFCS.2019.22},
  annote =	{Keywords: Knapsack, Approximation Algorithms, Multistage Optimization}
}

Keywords: Knapsack, Approximation Algorithms, Multistage Optimization
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI