Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D

Abstract

We revisit the $d$-dimensional Vector Knapsack problem ($d$-Knapsack): Given a $d$-dimensional capacity vector and a set of items, each with a $d$-dimensional weight vector and a profit, the goal is to select a set of items that maximizes the total profit without exceeding the capacity in any dimension. For any $d\ge 2$, the best known approximation scheme for $d$-Knapsack runs in time $O(n^{\lceil d/\epsilon \rceil -d})$ [Caprara, Kellerer, Pferschy, Pisinger '00]. We improve this running time to ${\tilde{O}}_{d,\epsilon ,\rho }(n^{\lceil \frac{d-1}{2\epsilon }-\frac{1}{2}+\rho \rceil }+n^d)$ for any $\epsilon \in (0,1)$ and every parameter $\rho \in (0,1)$. We achieve this speedup by designing the first meet-in-the-middle algorithm for $d$-Knapsack. This requires replacing the LP solver used in prior algorithms by a highly efficient dynamic programming algorithm to generate representative solutions, building on an LP-based structural argument. This is the first improvement in over 25 years, and the first result that improves the exponent by a constant factor. We complement this by a fine-grained lower bound based on $k$-SUM showing that 2-Knapsack requires time $n^{\lceil \frac{1}{2\epsilon }-\frac{1}{2}\rceil -o(1)}$. This establishes the optimal exponent of 2-Knapsack as $\frac{1}{2\epsilon }\pm O(1)$, which is precise up to an additive $O(1)$. To the best of our knowledge, this is the first result that determines the optimal exponent more precisely than up to a factor $O(1)$, for any problem that admits a PTAS but no EPTAS. For the special case of 2-Knapsack we further attain a $(1-\epsilon -\delta )$-approximation in time ${\tilde{O}}_{\delta ,\epsilon }(n^{\lceil \frac{1}{2\epsilon }-\frac{1}{2}\rceil })$. This nearly matches our lower bound, as for a slightly better approximation ratio a slightly better running time is impossible -- so our algorithm is bicriteria-optimal.

Abstract shortened to fit ArXiV requirements