Bounded Knapsack in Truly Subquadratic Time
cs.DS, cs.CG
Submitted: 2026-11-11
Updated: 2026-11-11
Terminology
Sources
- Knapsack with Small Items in Near-Quadratic Time
- 3SUM Made Simpler (Without Matrix Multiplication), k-SUM Hypothesis Refuted for Odd k, and Real 3SUM/APSP Derandomized
- Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
- Dense Subset Sum in Multi-Dimension
- Bounded Integer Programming in Almost N 2d Time
- Homogeneous structures in subset sums and non-averaging sets
- On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
- Solving Knapsack with Small Items via L0-Proximity
- 0-1 Knapsack in Nearly Quadratic Time
- On the Structure of $(\min,+)$ Convolution
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time