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 maximize total profit without exceeding the capacity in any dimension. For any $d\ge 2$, the best known approximation scheme runs in time $O(n^{\lceil d/\varepsilon\rceil-d})$ [Caprara et al., 2000]. We improve this to $\widetilde O_{d,\varepsilon,\rho}(n^{\lceil (d-1)/(2\varepsilon)-1/2+\rho\rceil}+n^{d})$ for $\varepsilon\in(0,1)$ and $\rho\in(0,1)$. The key is the first meet‑in‑the‑middle algorithm, which replaces the LP solver used previously with a highly efficient dynamic programming routine to generate representative solutions, based on an LP‑based structural argument. This is the first improvement in over 25 years and the first to reduce the exponent by a constant factor.
We also provide a fine‑grained lower bound based on $k$‑SUM, showing that 2‑Knapsack requires at least $n^{\lceil 1/(2\varepsilon)-1/2\rceil-o(1)}$ time. Hence the optimal exponent for 2‑Knapsack is $1/(2\varepsilon)\pm O(1)$, precise up to an additive constant. To our knowledge, this is the first result that pins down the optimal exponent to within a constant for any problem that admits a PTAS but no EPTAS.
For the special case of 2‑Knapsack we further achieve a $(1-\varepsilon-\delta)$‑approximation in $\widetilde O_{\delta,\varepsilon}(n^{\lceil 1/(2\varepsilon)-1/2\rceil})$ time. This nearly matches our lower bound; a slightly better approximation ratio would require a slightly higher running time, making the algorithm bicriteria‑optimal.
Blogger's Review: The paper delivers a breakthrough speed‑up for vector knapsack and, through a tight fine‑grained lower bound, precisely characterizes the 2‑dimensional case’s complexity. It sets a new benchmark for PTAS/EPTAS separations and will likely inspire further meet‑in‑the‑middle techniques in high‑dimensional optimization.