Knapsack and subset sum with small items

DOI10.4230/LIPICS.ICALP.2021.106MaRDI QIDQ7241206zbMATH OpenFDO

Authors Adam C. Polak, Lars Rohwedder, Karol Węgrzycki

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.106

zbMATH Keywords

additive combinatoricsknapsackmultisetproximitysubset sum

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A near-linear pseudopolynomial time algorithm for subset sum
• A simple near-linear pseudopolynomial time randomized algorithm for subset sum
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• Capacitated dynamic programming: faster knapsack and graph algorithms
• Fast algorithms for knapsack via convolution and prediction
• Fast and simple modular subset sum
• Fast Approximation Algorithms for Knapsack Problems
• Fast modular subset sum using linear sketching
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• scientific article; zbMATH DE number 7651168 (Why is no real title available?)
• scientific article; zbMATH DE number 7788444 (Why is no real title available?)
• scientific article; zbMATH DE number 7788445 (Why is no real title available?)
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Modular subset sum, dynamic strings, and zero-sum sets
• New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
• On integer programming and convolution
• On problems as hard as CNF-SAT
• On problems equivalent to \((\min,+)\)-convolution
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Saving space by algebraization
• SETH-based lower bounds for subset sum and bicriteria path
• Time bounds for selection
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

Cited in

(5)

• Even faster knapsack via rectangular monotone min-plus convolution and balancing
• Parameterized algorithms on integer sets with small doubling: integer programming, subset sum and k-SUM
• Does subset sum admit short proofs?
• Convolution and knapsack in higher dimensions
• Weakly approximating knapsack in subquadratic time

This page was built for publication: Knapsack and subset sum with small items

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241206)