Even faster knapsack via rectangular monotone min-plus convolution and balancing

DOI10.4230/LIPICS.ESA.2024.33MaRDI QIDQ7253089zbMATH OpenFDO

Authors Karl Bringmann, Anita Dürr, Adam C. Polak

Publication date 26 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2024.33

zbMATH Keywords

0-1-knapsack problembounded monotone min-plus convolutionfine-grained complexity

Mathematics Subject Classification ID

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
• Concentration of Measure for the Analysis of Randomized Algorithms
• Fast algorithms for knapsack via convolution and prediction
• Faster 0-1-knapsack via near-convex min-plus-convolution
• Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results
• Faster knapsack algorithms via bounded monotone min-plus-convolution
• Faster min-plus product for monotone instances
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Knapsack and subset sum with small items
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• On problems equivalent to \((\min,+)\)-convolution
• Reducibility among combinatorial problems
• Simple and faster algorithms for knapsack

Cited in

(1)

• Weakly approximating knapsack in subquadratic time

This page was built for publication: Even faster knapsack via rectangular monotone min-plus convolution and balancing

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