Abstract

We consider a natural resource allocation problem in which we are given a set of items, where each item has a list of pairs associated with it. Each pair is a configuration of an allowed size for this item, together with a nonnegative penalty, and an item can be packed using any configuration in its list. The goal is to select a configuration for each item so that the number of unit bins needed to pack the sizes plus the sum of penalties is minimized. This problem has applications in operating systems, bandwidth allocation, and discrete time-cost tradeoff planning problems. For the offline version of the problem we design an augmented asymptotic PTAS. That is, an asymptotic approximation scheme that uses bins of size slightly larger than 1. We further consider the online bounded space variant, where only a constant number of bins can be open simultaneously. We design a sequence of algorithms, where the sequence of their competitive ratios tends to the best possible asymptotic competitive ratio. Finally, we study the bin covering problem, in which a bin is covered if the sum of sizes allocated to it is at least 1. In this setting, penalties are interpreted as profits and the goal is to maximize the sum of profits plus the number of covered bins. We design an algorithm of best possible competitive ratio, which is 2. We generalize our results for online algorithms and unit sized bins to the case of variable sized bins, where there may be several distinct sizes of bins available for packing or covering, and get that the competitive ratios are again the same as for the more standard online problems. © 2008 Elsevier Inc. All rights reserved.