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 O (n + (1) ²) time Chen, Lian, Mao, and Zhang '24Mao '24. This running time is the best possible (up to a logarithmic factor), assuming that (, +) -convolution cannot be solved in truly subquadratic time K\"unnemann, Paturi, and Schneider '17Cygan, Mucha, Wegrzycki, and Wodarczyk '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 O (n + (1) ^2-) time for some constant > 0? We answer this open question affirmatively by proposing an O (n + (1) ^7/4) -time algorithm.
Chen et al. (Mon,) studied this question.