Capital Area Theory Seminar

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.

All of these problems are NP-hard and hence we focus on approximation algorithms. While the approximability of the 1-dimensional variants is well understood, there are large gaps in our understanding of the approximability of the multi-dimensional variants. Our work makes some progress in this direction. We design new approximation algorithms for vector scheduling and vector bin packing. Our approximation guarantees significantly improve upon some long standing bounds. We also obtain strong lower bounds on the approximability of these problems. In particular, we show that the randomized rounding technique of Raghavan and Thompson is indeed the best general technique for solving packing integer programs.

This is joint work with Chandra Chekuri (Bell Labs).

Contact: Vincenzo Liberatore (liberato@umiacs.umd.edu)