CONSTANT-RATIO APPROXIMATION FOR ROBUST BIN PACKING WITH BUDGETED UNCERTAINTY.

We consider robust variants of the bin packing problem with uncertain item sizes. Specifically we consider two uncertainty sets previously studied in the literature. The first is 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-cover 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 \scrP " \scrN \scrP) no asymptotic approximation scheme exists for the U\Gamma model, 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. [ABSTRACT FROM AUTHOR]