2024/07/14 by Doron-Arad, Ilan, Kulik, Ariel, Manurangsi, Pasin · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2407.10146
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\lceil d/ε \rceil - 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 ⋅ Wd)-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/ε))2)-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(d2) + nO(1)-time Ω(1/√(d))-approximation and a matching nO(1)-time lower~bound.