On Multidimensional Packing Problems

TLDR

The vector scheduling problem seeks to minimize the maximum load across dimensions on m machines, while the vector bin packing problem aims to minimize the number of bins needed to pack n tasks with bounded load per dimension; these problems arise from scheduling tasks with multiple resource requirements and are related to packing integer programs that maximize vectors in a unit‑height bin. The authors investigate the approximability of multidimensional generalizations of multiprocessor scheduling, bin packing, and knapsack, focusing on vector scheduling, its dual vector bin packing, and related packing integer programs. They analyze these problems using algorithmic techniques and hardness reductions to establish approximation bounds. The study yields new algorithmic results and inapproximability bounds for vector scheduling, vector bin packing, and packing integer programs.

Abstract

We study the approximability of multidimensional generalizations of three classical packing problems: 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 nd -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. Finally, packing integer programs capture a core problem that directly relates to both vector scheduling and vector bin packing, namely, the problem of packing a maximum number of vectors in a single bin of unit height. We obtain a variety of new algorithmic as well as inapproximability results for these three problems.