This paper deals with the min-max version of the problem of selecting
p items of the minimum total weight out of a set of n items, where the item weights are uncertain. The discrete scenario representation of uncertainty is considered. The computational complexity of the problem is explored. A randomized algorithm for the problem is then proposed, which returns an
O(lnK)-approximate solution with a high probability, where
K is the number of scenarios. This is the first approximation algorithm with better than
K worst case ratio for the class of min-max combinatorial optimization problems with unbounded scenario set.
