Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing

Speaker(s)

Anita Dürr

Affiliation

Max Planck Institute for Informatics

Language of the talk

English

Date

Nov. 8, 2024, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time ˜O(n + t√pmax), where n is the number of items, t is the knapsack capacity, and pmax is the maximum item profit. This improves over the ˜O(n + t pmax)-time algorithm based on the convolution and prediction technique by Bateni et al. (STOC 2018). Moreover, we give some evidence, based on a strengthening of the Min-Plus Convolution Hypothesis, that our running time might be optimal. Our algorithm uses two new technical tools, which might be of independent interest. First, we generalize the ˜O(n^1.5)-time algorithm for bounded monotone min-plus convolution by Chi et al. (STOC 2022) to the rectangular case where the range of entries can be different from the sequence length. Second, we give a reduction from general knapsack instances to balanced instances, where all items have nearly the same profit-to-weight ratio, up to a constant factor. Using these techniques, we can also obtain algorithms that run in time ˜O(n + OPT√wmax), ˜O(n + (n*wmax*pmax)^{1/3}*t^{2/3}), and ˜O(n + (n*wmax*pmax)^{1/3}*OPT^{2/3}), where OPT is the optimal total profit and wmax is the maximum item weight.

This result was published at ESA'24 and received the best paper award for track A.

---