On multidimensional packing problems

Chandra Chekuri, Sanjeev Khanna

Research output: Contribution to journalArticlepeer-review


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 n d-dimenaional 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.

Original languageEnglish (US)
Pages (from-to)837-851
Number of pages15
JournalSIAM Journal on Computing
Issue number4
StatePublished - May 2004
Externally publishedYes


  • Approximation algorithms
  • Bin packing
  • Combinatorial optimization
  • Hardness of approximation
  • Knapsack
  • Multidimensional packing
  • Multiprocessor scheduling
  • Packing integer programs
  • Vector bin packing
  • Vector scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'On multidimensional packing problems'. Together they form a unique fingerprint.

Cite this