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 + \varepsilon)$ and total weight at most $t$, then Knapsack can be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^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 + \varepsilon)t$. Therefore, it is natural to ask the following question. If one seeks a solution with total profit at least $\mathrm{OPT}/(1+\varepsilon)$ and total weight at most $(1 + \varepsilon)t$, can Knsapck be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^{2-δ})$ time for some constant $δ> 0$? We answer this open question affirmatively by proposing an $\tilde{O}(n + (\frac{1}{\varepsilon})^{7/4})$-time algorithm.

We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set$X$of$n$positive integers and a target$t$, Subset Sum asks whether some subset of$X$sums to$t$. Bringmann proposes an$\tilde{O}(n+t)$-time algorithm [Bringmann SODA'17], and an open question has naturally arisen: can Subset Sum be solved in$O(n+w)$time? Here$w$is the maximum integer in$X$. We make a progress towards resolving the open question by proposing an$\tilde{O}(n+\sqrt{wt})$-time algorithm.

We investigate pseudopolynomial-time algorithms for Bounded Knapsack and Bounded Subset Sum. Recent years have seen a growing interest in settling their fine-grained complexity with respect to various parameters. For Bounded Knapsack, the number of items n and the maximum item weight wmax are two of the most natural parameters that have been studied extensively in the literature. The previous best running time in terms of n and wmax is [Polak, Rohwedder, Węgrzycki ‘21]. There is a conditional lower bound of (n + wmax)2-o(1) based on (min, +)-convolution hypothesis [Cygan, Mucha, Węgrzycki, Włodarczyk ‘17]. We narrow the gap significantly by proposing an -time algorithm. Our algorithm works for both 0-1 Knapsack and Bounded Knapsack. Note that in the regime where wmax ≈ n, our algorithm runs in Õ(n12/5) time, while all the previous algorithms require Ω(n3) time in the worst case.

We investigate the classic Knapsack problem and propose a fully polynomial-time approximation scheme (FPTAS) that runs in O(n + (1/)2) time. Prior to our work, the best running time is O(n + (1/)11/5) [Deng, Jin, and Mao’23]. Our algorithm is the best possible (up to a polylogarithmic factor), as Knapsack has no O((n + 1/)2−δ)-time FPTAS for any constant δ > 0, conditioned on the conjecture that (min, +)-convolution has no truly subquadratic-time algorithm.

We propose an O(n + 1/)-time FPTAS (Fully Polynomial-Time Approximation Scheme) for the classical Partition problem. This is the best possible (up to a polylogarithmic factor) assuming SETH (Strong Exponential Time Hypothesis) [Abboud, Bringmann, Hermelin, and Shabtay’22]. Prior to our work, the best known FPTAS for Partition runs in O(n + 1/5/4) time [Deng, Jin and Mao’23, Wu and Chen’22]. Our result is obtained by solving a more general problem of weakly approximating Subset Sum.