Knapsack with Small Items in Near-Quadratic Time
Preprint
Abstract
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 $w_{\mathrm{max}}$ and the number of items $n$. A conditional lower bound rules out that Knapsack can be solved in time $O((n+w_{\mathrm{max}})^{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 $\tilde O((n+w_{\mathrm{max}})^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 $\tilde O(n^3 w_{\mathrm{max}}^2)$ [Tamir'09], $\tilde O(n^2 w_{\mathrm{max}}^2)$ and $\tilde O(n w_{\mathrm{max}}^3)$ [Bateni, Hajiaghayi, Seddighin, Stein'18], $O(n^2 w_{\mathrm{max}}^2)$ and $\tilde O(n w_{\mathrm{max}}^2)$ [Eisenbrand and Weismantel'18], $O(n + w_{\mathrm{max}}^3)$ [Polak, Rohwedder, Wegrzycki'21], and very recently $\tilde O(n + w_{\mathrm{max}}^{12/5})$ [Chen, Lian, Mao, Zhang'23]. In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time $\tilde O(n + w_{\mathrm{max}}^2)$, which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- On Near-Linear-Time Algorithms for Dense Subset Sum2021
- A Subquadratic Approximation Scheme for Partition2019
- A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum2017
- New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problemsOperations Research Letters, 2009
- Improved Dynamic Programming in Connection with an FPTAS for the Knapsack ProblemJournal of Combinatorial Optimization, 2004
- Linear Time Algorithms for Knapsack Problems with Bounded WeightsJournal of Algorithms, 1999
- New analytical results in subset-sum problemDiscrete Mathematics, 1993
- An Almost Linear-Time Algorithm for the Dense Subset-Sum ProblemSIAM Journal on Computing, 1991
- Solving dense subset-sum problems by using analytical number theoryJournal of Complexity, 1989
- Geometric applications of a matrix-searching algorithmAlgorithmica, 1987