Tight Bounds for Online Class-Constrained Packing

Abstract

We consider class constrained packing problems, in which we are given a set of bins, each having a capacity v and c compartments, and n items of M different classes and the same (unit) size. We need to fill the bins with items, subject to capacity constraints, such that items of different classes are placed in separate compartments; thus, each bin can contain items of at most c distinct classes. We consider two optimization goals. In the class-constrained bin-packing problem (CCBP), our goal is to pack all the items in a minimal number of bins; in the class-constrained multiple knapsack problem (CCMK), we wish to maximize the total number of items packed in m bins, for m >> 1. The CCBP and CCMK model fundamental resource allocation problems in computer and manufacturing systems. Both are known to be strongly NP-hard.

In this paper we derive tight bounds for the online variants of these problems. We first present a lower bound of (1 + α) on the competitive ratio of any deterministic algorithm for the online CCBP, where α ∈ (0, 1] depends on v, c,M and n. We show that this ratio is achieved by the algorithm first-fit.

We then consider the temporary CCBP, in which items may be packed for a bounded time interval (that is unknown in advance). We obtain a lower bound of v/c on the competitive ratio of any deterministic algorithm. We show that this ratio is achieved by all any-fit algorithms.

Finally, tight bounds are derived for the online CCMK and the temporary CCMK problems.

On leave from the Department of Computer Science, Technion, Haifa 32000, Israel.