AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We present pseudopolynomial-time algorithms for the Knapsack problem that has running time ˜O(n + W√pmax) and ˜O(n + (n * wmax* pmax)1/3 W^2/3), where n is the number of items, W is the knapsack capacity, pmax is the maximum item profit and wmax is the maximum item weight. This improves over the ˜O(n + W 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(n1.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. This will be a high-level talk. It is about motivation, results and intuition, not about proofs or technical details.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

649 2184 1396

passcode not visible

logged in users only