Key points are not available for this paper at this time.
We study the approximability of multi-dimensional generalizations of the classical problems of multiprocessor scheduling, bin packing and the knapsack problem. Specifically, we study the vector scheduling problem, its dual problem, namely, the vector bin packing problem, and a class of packing integer programs. The vector scheduling problem is to schedule n d-dimensional tasks on m machines such that the maximum load over all dimensions and all machines is minimized. The vector bin packing problem, on the other hand, seeks to minimize the number of bins needed to schedule all n tasks such that the maximum load on any dimension across all bins is bounded by a fixed quantity, say 1. Such problems naturally arise when scheduling tasks that have multiple resource requirements. We obtain a variety of new algorithmic as well as inapproximability results for these problems. For vector scheduling, we give a PTAS when d is a fixed constant, and an O(minflog dm; log 2 dg)-approximation in gen...
Chekuri et al. (Thu,) studied this question.