  Multidimensional packing problems generalize the classical 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. In this
paper, we close this gap by giving almost tight hardness results for these
problems.
  1. We show that Vector Bin Packing has no polynomial time $\Omega( \log d)$
factor asymptotic approximation algorithm when $d$ is a large constant,
assuming $\textsf{P}\neq \textsf{NP}$. This matches the $\ln d + O(1)$ factor
approximation algorithms (Chekuri, Khanna SICOMP 2004, Bansal, Caprara,
Sviridenko SICOMP 2009, Bansal, Eli\'{a}s, Khan SODA 2016) upto constants.
  2. We show that Vector Scheduling has no polynomial time algorithm with an
approximation ratio of $\Omega\left( (\log d)^{1-\epsilon}\right)$ when $d$ is
part of the input, assuming $\textsf{NP}\nsubseteq \textsf{ZPTIME}\left(
n^{(\log n)^{O(1)}}\right)$. This almost matches the $O\left( \frac{\log
d}{\log \log d}\right)$ factor algorithms(Harris, Srinivasan JACM 2019, Im,
Kell, Kulkarni, Panigrahi SICOMP 2019). We also show that the problem is
NP-hard to approximate within $(\log \log d)^{\omega(1)}$.
  3. We show that Vector Bin Covering is NP-hard to approximate within
$\Omega\left( \frac{\log d}{\log \log d}\right)$ when $d$ is part of the input,
almost matching the $O(\log d)$ factor algorithm (Alon et al., Algorithmica
1998).
  Previously, no hardness results that grow with $d$ were known for Vector
Scheduling and Vector Bin Covering when $d$ is part of the input and for Vector
Bin Packing when $d$ is a fixed constant.
