Weakly Approximating Knapsack in Subquadratic Time

Abstract

We consider the classic Knapsack problem. Let $t$ and $\mathrm{OPT}$ be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least $\mathrm{OPT}/(1+\epsilon )$ and total weight at most $t$, then Knapsack can be solved in $\tilde{O}(n+(\frac{1}{\epsilon }{)}^2)$ time [Chen, Lian, Mao, and Zhang '24][Mao '24]. This running time is the best possible (up to a logarithmic factor), assuming that $(\min ,+)$-convolution cannot be solved in truly subquadratic time [Künnemann, Paturi, and Schneider '17][Cygan, Mucha, Węgrzycki, and Włodarczyk '19]. The same upper and lower bounds hold if one seeks a solution with total profit at least $\mathrm{OPT}$ and total weight at most $(1+\epsilon )t$. Therefore, it is natural to ask the following question. If one seeks a solution with total profit at least $\mathrm{OPT}/(1+\epsilon )$ and total weight at most $(1+\epsilon )t$, can Knsapck be solved in $\tilde{O}(n+(\frac{1}{\epsilon }{)}^{2-\hat{I}´})$ time for some constant $\hat{I}´>0$? We answer this open question affirmatively by proposing an $\tilde{O}(n+(\frac{1}{\epsilon }{)}^{7/4})$-time algorithm.

To appear in ICALP2025