Knapsack with Small Items in Near-Quadratic Time

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
subquadratic time in terms of n + wmax [Cygan, Mucha, Wegrzycki,
Wlodarczyk’17, Künnemann, Paturi, Schneider’17]. This raised the
question whether Knapsack can be solved in (near-)quadratic time in
terms of n + wmax. The quest of resolving this question lead to various
improved algorithms [Tamir’09, Bateni, Hajiaghayi, Seddighin, Stein’18,
Eisenbrand, Weismantel’18, Axiotis, Tzamos'19, Polak, Rohwedder,
Wegrzycki’21, Jin'23, Chen, Lian, Mao, Zhang’23]. In this work we
resolve this question by designing an algorithm for Knapsack with
near-quadratic time in terms of n + wmax, which is conditionally
near-optimal.

This is a practice talk and recording for STOC'24.