ECCC-Report TR21-007https://eccc.weizmann.ac.il/report/2021/007Comments and Revisions published for TR21-007en-usMon, 18 Jan 2021 18:02:07 +0200
Paper TR21-007
| Almost Optimal Inapproximability of Multidimensional Packing Problems |
Sai Sandeep
https://eccc.weizmann.ac.il/report/2021/007Multidimensional 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 $\Omega( \log d)$ factor asymptotic approximation algorithm when $d$ is a large constant, assuming $P \neq NP$. This matches the $\ln d + O(1)$ factor approximation algorithms (Chekuri, Khanna SICOMP 2004, Bansal, Caprara, Sviridenko SICOMP 2009, Bansal, Eliáš, 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 NP has no quasipolynomial time algorithms. 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. Mon, 18 Jan 2021 18:02:07 +0200https://eccc.weizmann.ac.il/report/2021/007