Convolution and knapsack in higher dimensions

DOI10.4230/LIPICS.WADS.2025.30MaRDI QIDQ7312580zbMATH OpenFDO

Authors Kilian Grage, Klaus Jansen, Björn Schumacher

Publication date 11 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.WADS.2025.30

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites work

• A near-linear pseudopolynomial time algorithm for subset sum
• Capacitated dynamic programming: faster knapsack and graph algorithms
• Clustered Integer 3SUM via Additive Combinatorics
• Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results
• Faster all-pairs shortest paths via circuit complexity
• Faster min-plus product for monotone instances
• Fine-grained equivalence for problems related to integer linear programming
• Grundzüge einer arithmetischen Theorie der algebraischen Grössen. (Festschrift zu Herrn Ernst Eduard Kummers fünfzigjährigem Doctor-Jubiläum, 10 September 1881)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• Improving proximity bounds using sparsity
• Improving the Cook et al. proximity bound given integral valued constraints
• Knapsack and subset sum with small items
• Necklaces, Convolutions, and X + Y
• On problems equivalent to \((\min,+)\)-convolution
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Simple multivariate polynomial multiplication
• Structured ( ,+)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• Time bounds for selection

This page was built for publication: Convolution and knapsack in higher dimensions

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