我们重新审视$d$维向量背包问题（$d$-Knapsack）：给定$d$维容量向量和若干物品，每个物品有$d$维重量向量和收益，目标是在不超容量的前提下最大化总收益。对任意$d\ge 2$，已有的最佳近似方案时间为 $O(n^{\lceil d/\varepsilon\rceil-d})$ [Caprara 等 2000]。本文将运行时间改进至 $\widetilde O_{d,\varepsilon,\rho}(n^{\lceil (d-1)/(2\varepsilon)-1/2+\rho\rceil}+n^{d})$，其中 $\varepsilon\in(0,1)$，$\rho\in(0,1)$。核心是设计首个 meet-in-the-middle 算法，使用高效的动态规划替代之前的线性规划求解器，以生成代表性解，并基于 LP 结构论证。该结果是 25 年来的首次改进，也是首次将指数常数因子降低。
我们进一步给出基于 $k$-SUM 的细粒度下界，证明 2‑Knapsack 至少需要时间 $n^{\lceil 1/(2\varepsilon)-1/2\rceil-o(1)}$。因此 2‑Knapsack 的最优指数为 $1/(2\varepsilon)\pm O(1)$，精确到常数项。这是首个在 PTAS 存在但 EPTAS 不存在的问题上，将最优指数确定到常数误差以内的结果。
针对 2‑Knapsack 的特殊情形，我们还能在 $\widetilde O_{\delta,\varepsilon}(n^{\lceil 1/(2\varepsilon)-1/2\rceil})$ 时间内得到 $(1-\varepsilon-\delta)$ 近似。该算法几乎匹配下界，若要求更好的近似比则需要更高的时间复杂度——因此算法在双准则意义下是最优的。
博主点评：这篇工作在向量背包领域实现了突破性的加速，并通过细粒度下界明确了 2‑维情形的复杂度极限，为后续 PTAS/EPTAS 的细致划分提供了重要参考。