Today the ATMOS conference takes place in Aarhus as part of the ALGO meeting. Just in time, the proceedings have been published with quite some great papers, so I’m much looking forward to the talks today. Invited speaker of this year’s ATMOS is Thomas Schlechte, who also happens to be co-author of the paper we awarded the Best Paper Award to.

Aarhus itself is quite a wonderful city, and my way from the hotel to university takes me right through the city centre. Next year’s European Capital of Culture, there is quite a lot to see! And to eat, as far as what little capacity the conference generosity leaves. I’m quite taken by the Kanelsnegl that seem to be typical around here.

Improvable Knapsack Problems

In combinatorial optimisation problem, we are usually given a set of elements and need to decide for each element if we want to use it or not. Additional constraints will need to be respected.

For the knapsack problem, for example, we decide for each item if we want to pack it or not. We recently considered a variant of this problem, where we do not only decide if to pack or not to pack, but we can also choose between different versions of the item: There is a separate budget available that we can spend to improve items. Imagine you pack your suitcase, and you might spend some money to exchange your heavy old coat for a lighter jacket with more modern fibres.

Of course this doesn’t make matters easier. If you can spend your improvements continuously (i.e., you can buy “half improvements”), we were able to show amongst other results that the problem can be decomposed into a series of subproblems which are not quite knapsack problems with two knapsack constraints. This in turn leads to a PTAS for the problem.

This is the abstract:

We consider a variant of the knapsack problem, where items are available with different possible weights. Using a separate budget for these item improvements, the question is: Which items should be improved to which degree such that the resulting classic knapsack problem yields maximum profit?
We present a detailed analysis for several cases of improvable knapsack problems, presenting constant factor approximation algorithms and two PTAS.