Lunedì 24 settembre 2018 alle ore 12.00, presso la sala riunioni della sez. di Informatica e Automazione del Dipartimento di Ingegneria dell’Università Roma Tre, il prof. Ulrich Pferschy dell’Università di Graz terrà un seminario dal titolo:

Approximating the Incremental Knapsack Problem

Abstract:

We consider the 0-1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The contribution of a packed item in each time period depends on its profit as well as on a time factor which reflects the importance of the period in the objective function. The problem calls for maximizing the weighted sum of the profits over the whole time horizon.

In this work, we provide approximation results for IKP and its restricted variants. In some results, we rely on Linear Programming (LP) to derive approximation bounds. We first manage to prove the tightness of some approximation ratios of a general purpose algorithm currently available in the literature and originally applied to a time-invariant version of the problem. We also devise a Polynomial Time Approximation Scheme (PTAS) when the input value indicating the number of periods is considered as a constant. Then, we add the mild and natural assumption that each item can be packed in the first time period. For this variant, we discuss different approximation algorithms suited for any number of time periods and for the special case with two periods.

Joint work with Federico Della Croce and Rosario Scatamacchia

Per informazioni rivolgersi a G. Nicosia (nicosia@ing.uniroma3.it, tel. 06 57333455)