2026-07-26T11:03:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21104 2024-09-23T09:13:16Z ddc:004 open_access

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing Bringmann, Karl Dürr, Anita Polak, Adam 0-1-Knapsack problem bounded monotone min-plus convolution fine-grained complexity We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time Õ(n + t√{p_{max}}), where n is the number of items, t is the knapsack capacity, and p_{max} is the maximum item profit. This improves over the Õ(n + t p_{max})-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 Õ(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 Õ(n + OPT√{w_{max}}), Õ(n + (nw_{max}p_{max})^{1/3}t^{2/3}), and Õ(n + (nw_{max}p_{max})^{1/3} OPT^{2/3}), where OPT is the optimal total profit and w_{max} is the maximum item weight. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karl Bringmann and Anita Dürr and Adam Polak 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.33 urn:nbn:de:0030-drops-211047 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.33 eng https://creativecommons.org/licenses/by/4.0/legalcode