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(nd/ε - d). Unfortunately, existing lower bounds only cover the special case with two dimensions $d = 2$, and do not answer whether there is a no(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 no(d/ε · 1/(log(d/ε))²)-time (1-ε)-approximation for every ε = O(1/log d). No (n+W)o(d/log d)-time exact algorithm (assuming ETH). No no(√d)-time (1-ε)-approximation for constant ε. (d · log W)O(d²) + nO(1)-time Ω(1/√d)-approximation and a matching nO(1)-time lower~bound.