2023/08/14 by Xiao Mao, Mao, Xiao · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2308.07004
openalex publication_date 2023/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Knapsack is one of the most fundamental problems in theoretical computer science. In the (1 - ε)-approximation setting, although there is a fine-grained lower bound of (n + 1 / ε) ^ 2 - o(1) based on the (min, +)-convolution hypothesis ([Künnemann, Paturi and Stefan Schneider, ICALP 2017] and [Cygan, Mucha, Wegrzycki and Wlodarczyk, 2017]), the best algorithm is randomized and runs in O(n + (\frac1ε)11/5/2Ω(√(log(1/ε)))) time [Deng, Jin and Mao, SODA 2023], and it remains an important open problem whether an algorithm with a running time that matches the lower bound (up to a sub-polynomial factor) exists. We answer the question positively by showing a deterministic (1 - ε)-approximation scheme for knapsack that runs in O(n + (1 / ε) ^ 2) time. We first extend a known lemma in a recursive way to reduce the problem to n ε-additive approximation for n items with profits in [1, 2). Then we give a simple efficient geometry-based algorithm for the reduced problem.