Abstract: Multidimensional packing problems generalize the standard packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be d-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. We close this gap by giving almost optimal inapproximability results for the multidimensional problems, namely, Vector Bin Packing, Vector Scheduling, and Vector Bin Covering.
For the Vector Bin Packing problem, our hardness result goes via the hardness of the set cover problem using a notion of packing dimension of set families. For the Vector Scheduling and Vector Bin Covering problems, we obtain our hardness results via variants of graph and hypergraph coloring problems.