2023/08/06 by Karl Bringmann, Bringmann, Karl
Computer Science · Engineering · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2308.03075
openalex publication_date 2023/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research worked towards understanding the complexity of pseudopolynomial-time algorithms for Knapsack parameterized by the maximum item weight wmax and the number of items n. A conditional lower bound rules out that Knapsack can be solved in time O((n+wmax)2-δ) for any δ> 0 [Cygan, Mucha, Wegrzycki, Wlodarczyk'17, Künnemann, Paturi, Schneider'17]. This raised the question whether Knapsack can be solved in time O((n+wmax)2). This was open both for 0-1-Knapsack (where each item can be picked at most once) and Bounded Knapsack (where each item comes with a multiplicity). The quest of resolving this question lead to algorithms that solve Bounded Knapsack in time O(n3 wmax2) [Tamir'09], O(n2 wmax2) and O(n wmax3) [Bateni, Hajiaghayi, Seddighin, Stein'18], O(n2 wmax2) and O(n wmax2) [Eisenbrand and Weismantel'18], O(n + wmax3) [Polak, Rohwedder, Wegrzycki'21], and very recently O(n + wmax12/5) [Chen, Lian, Mao, Zhang'23]. In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time O(n + wmax2), which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.