- FR
- EN
We start the talk by introducing main concepts in robust combinatorial optimization. We will review the basic hardness result for arbitrary uncertainty sets and the key results from Bertsimas and Sim for budgeted uncertainty, including its extension to knapsack uncertainty. In a second step, we focus on the bin-packing problem where the sizes of the items can take any value in a given uncertainty set $U\subseteq \times_{i=1}^n[\overline{a}_i,\overline{a}_i+\hat{a}_i]$, where $\overline{a}\in[0,1]^n$ represents the nominal sizes of the items and $\hat{a}\in[0,1]^n$ their possible deviations. We consider more specifically two uncertainty sets previously studied in the literature. The first set, denoted $U^\Gamma$, contains scenarios in which at most $\Gamma\in\mathbb{Z}$ items deviate, each of them reaching its peak value $\overline{a}_i+\hat{a}_i$, while each other item has its nominal value $\overline{a}_i$. The second set, denoted $U^\Omega$, bounds by $\Omega\in[0,1]$ the total amount of deviation in each scenario. We show that a variant of the next-fit algorithm provides a $2$-approximation for model $U^\Omega$, and a $2(\Gamma+1)$ approximation for model $U^\Gamma$ (which can be improved to $2$ approximation for $\Gamma=1$). This motivates the question of the existence of a constant ratio approximation algorithm for the $U^\Gamma$ model. Our main result is to answer positively to this question by providing a $4.5$ approximation for $U^\Gamma$ model based on dynamic programming.
