Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 26, 2013, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Yann Disser (TU Berlin)
We consider the classical knapsack problem with the twist that we do not know the capacity of the knapsack a priori. We are given a set of items, each with a size and a value. Once an item is put into the knapsack, it cannot be taken out again, and whenever an item doesn't fit, we may discard the item and continue to fill the knapsack with the remaining items. Our goal is to put the items into a universal order, such that trying to pack the items in this order gives a good solution for every capacity. We give an algorithm that always produces an ordering that achieves a 2-approximation of the optimum solution for every capacity. The algorithm does this by emulating the classical greedy 2-approximation algorithm for the standard knapsack problem. We also show that this algorithm is best-possible in the sense that for some instances no ordering can achieve a better ratio for all capacities.
Automatic MiSe System Software Version 1.4803M | admin login