2026-08-11T07:40:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14175 2024-03-06T10:53:40Z ddc:004 open_access

Knapsack and Subset Sum with Small Items Polak, Adam Rohwedder, Lars Węgrzycki, Karol Knapsack Subset Sum Proximity Additive Combinatorics Multiset Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In this paper we focus on the maximum item size s and the maximum item value v. We give algorithms that run in time O(n + s³) and O(n + v³) for the Knapsack problem, and in time Õ(n + s^{5/3}) for the Subset Sum problem. Our algorithms work for the more general problem variants with multiplicities, where each input item comes with a (binary encoded) multiplicity, which succinctly describes how many times the item appears in the instance. In these variants n denotes the (possibly much smaller) number of distinct items. Our results follow from combining and optimizing several diverse lines of research, notably proximity arguments for integer programming due to Eisenbrand and Weismantel (TALG 2019), fast structured (min,+)-convolution by Kellerer and Pferschy (J. Comb. Optim. 2004), and additive combinatorics methods originating from Galil and Margalit (SICOMP 1991). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Polak and Lars Rohwedder and Karol Węgrzycki 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.106 urn:nbn:de:0030-drops-141752 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.106 eng https://creativecommons.org/licenses/by/4.0/legalcode