Fine Grained Lower Bounds for Multidimensional Knapsack

We study the d-dimensional knapsack problem. We are given a set of items, each with a d-dimensional cost vector and a profit, along with a d-dimensional budget vector. The goal is to select a set of items that do not exceed the budget in all dimensions and maximize the total profit. A PTAS with running time n^ (d/) has long been known for this problem, where is the error parameter and n is the encoding size. Despite decades of active research, the best running time of a PTAS has remained O (n^ d/ - d). Unfortunately, existing lower bounds only cover the special case with two dimensions d = 2, and do not answer whether there is a n^o (d/) -time PTAS for larger values of d. The status of exact algorithms is similar: there is a simple O (n Wᵈ) -time (exact) dynamic programming algorithm, where W is the maximum budget, but there is no lower bound which explains the strong exponential dependence on d. In this work, we show that the running times of the best-known PTAS and exact algorithm cannot be improved up to a polylogarithmic factor assuming Gap-ETH. Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP constraints into a desired number of dimensions, exhibiting tight trade-off between d and for most regimes of the parameters. Informally, we obtain the following main results for d-dimensional knapsack. No n^o (d/ 1/ ( (d/) ) ²) -time (1-) -approximation for every = O (1/ d). No (n+W) ^o (d/ d) -time exact algorithm (assuming ETH). No n^o (d) -time (1-) -approximation for constant. (d W) ^O (d²) + n^O (1) -time (1/d) -approximation and a matching n^O (1) -time lower~bound.