Résumé
We consider robust variants of the bin packing problem with uncertain item sizes. Specifically we consider two uncertainty sets previously studied in the literature: budgeted uncertainty (the $U^\Gamma$ model) in which at most $\Gamma$ items deviate, each reaching its peak value, while other items assume their nominal values. The second uncertainty set, the $U^\Omega$ model, bounds the total amount of deviation in each scenario. We show that a variant of the next-fit-decreasing algorithm is a $2$ approximation for the $U^\Omega$ model, and another variant of this algorithm is a $2\Gamma$ approximation for the $U^\Gamma$ model. Unlike the classical bin packing problem, it is shown that (unless $P$=$NP$) no asymptotic approximation scheme exists for the $U^\Gamma$ model, already for $\Gamma=1$. This motivates the question of the existence of a constant approximation factor algorithm for the $U^\Gamma$ model. Our main result is to answer this question by proving a (polynomial-time) $4.5$ approximation algorithm, based on a dynamic-programming approach.