Weakly approximating knapsack in subquadratic time

DOI10.4230/LIPICS.ICALP.2025.51MaRDI QIDQ7346487zbMATH OpenFDO

Authors Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

Cites work

• A faster FPTAS for the unbounded knapsack problem
• A near-linear pseudopolynomial time algorithm for subset sum
• A new fully polynomial time approximation scheme for the Knapsack problem
• A subquadratic approximation scheme for partition
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Approximating Knapsack and partition via dense subset sums
• Capacitated dynamic programming: faster knapsack and graph algorithms
• Clustered Integer 3SUM via Additive Combinatorics
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Even faster knapsack via rectangular monotone min-plus convolution and balancing
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• 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 all-pairs shortest paths via circuit complexity
• Faster knapsack algorithms via bounded monotone min-plus-convolution
• Faster min-plus product for monotone instances
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• scientific article; zbMATH DE number 7788446 (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
• Necklaces, convolutions, and \(X+Y\)
• On problems equivalent to \((\min,+)\)-convolution
• Online knapsack with resource augmentation
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Reducibility among combinatorial problems

This page was built for publication: Weakly approximating knapsack in subquadratic time

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