Answers are grounded in this paper and cite their sources.
The study demonstrates an algorithm solving knapsack with optimal value in subquadratic time, suggesting new bounds for total profit.
We consider the classic Knapsack problem. Let t and OPT be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least OPT/(1 + ε) and total weight at most t, then Knapsack can be solved in Õ(n + (1/ε)²) 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\"unnemann, Paturi, and Schneider '17][Cygan, Mucha, W{e}grzycki, and W{}odarczyk '19]. The same upper and lower bounds hold if one seeks a solution with total profit at least OPT and total weight at most (1 + ε)t. Therefore, it is natural to ask the following question. If one seeks a solution with total profit at least OPT/(1+ε) and total weight at most (1 + ε)t, can Knsapck be solved in Õ(n + (1/ε)2-δ) time for some constant δ > 0? We answer this open question affirmatively by proposing an Õ(n + (1/ε)7/4)-time algorithm.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: