**Tuesday, 16:15 - 16:40 h, Room: MA 042**

**Ulrich Pferschy**

On the robust knapsack problem

**Coauthor: Michele Monaci**

**Abstract:**

We consider an uncertain variant of the knapsack problem that arises when the exact weight of each item is not exactly known in advance but belongs to a given interval, and the number of items whose weight differs from the nominal value but attains an arbitrary value in this interval is bounded by a constant. We analyze the worsening of the optimal solution value with respect to the classical knapsack problem, and exactly determine its worst-case performance depending on uncertainty for all parameter configurations. In addition, we perform the same analysis for the fractional version of the problem and provide an efficient, nontrivial algorithm for its solution. Finally, we derive the worst-case performance ratio of the fractional problem and of a variant of the greedy algorithm for the robust knapsack problem.

Talk 3 of the invited session Tue.3.MA 042

**"Theory of robust optimization"** [...]

Cluster 20

**"Robust optimization"** [...]