2025/04/21 by Chen, Lin, Lian, Jiayi, Mao, Yuchen +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2504.15001
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)/(ε))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 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.