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.

Advertisements