← All papers
First page of Bounded Knapsack in Truly Subquadratic Time

Bounded Knapsack in Truly Subquadratic Time

Huanyi Zhou

cs.DS Nov 11, 2026 · v1 cs.CG
Cites a Lean 4 development at a specific commit as a machine-checked artifact supporting the paper's results.
Bounded Knapsack asks how many copies of each item to take to maximize profit under a capacity constraint. Given $n$ records with binary-encoded multiplicities, we return optimal counts in randomized time with a fixed power saving in the maximum item weight $w_{\max}$ or maximum item profit $p_{\max}$. Fix $1<ρ<2$ and suppose integer $(\min,+)$-convolution on length-$m$ arrays can be computed with failure probability at most $η$ in $\widetilde O(m^ρ)$ time, up to polynomial factors in the entry bit length and $\log(1/η)$. Put $f(ρ)=4(3-ρ)/(8-3ρ).$ For any fixed $ε>0$, on inputs whose integers have magnitude polynomial in $n+\min(w_{\max},p_{\max})$, our algorithm runs in time $$\widetilde O\bigl(n\min(w_{\max},p_{\max})^{f(ρ)+ε}\bigr).$$ It returns optimal counts with high probability. If convolution saves $δ=2-ρ$ in its exponent, knapsack retains $δ/(1+3δ/2)$. With the integer convolution exponent $1.9601397040925$, a separate parameter choice gives $\widetilde O(n+\min(w_{\max},p_{\max})^{1.961})$, including for 0-1 Knapsack. We keep the copies compressed. Witnessed convolutions generate residual queries, and local linear programs filter them by cost. Resilient lattice cores allow recursive states to coalesce. Progression reserves support rounding, and a thin affordable fiber yields a lift that reduces the normalized column volume. This volume bounds the number of LP regions a grid lookup examines.

Bounded Knapsack with binary-encoded multiplicities had deterministic near-quadratic algorithms in the maximum item weight or profit. A truly subquadratic algorithm was open. The conditional barrier from the (min,+)-convolution hypothesis was removed once truly subquadratic integer (min,+)-convolution became available.

Copies are kept compressed, and proximity confines optima to O(w_max) copies per weight class. Recursive transfers use witnessed (min,+)-convolutions to generate residual queries, which local linear programs filter by cost. Resilient lattice cores let recursive states coalesce, and progression reserves support rounding. Lifts reduce a normalized column volume that bounds grid-atlas lookups. A Lean 4 development is cited as an accompanying artifact; the extracted text does not show what it formalizes.

Given a (min,+)-convolution exponent ρ<2, Bounded Knapsack runs in randomized time Õ(n + min(w_max,p_max)^{f(ρ)+ε}) with f(ρ)=4(3-ρ)/(8-3ρ). With the known integer convolution exponent 1.9601..., a separate parameter choice gives Õ(n + min(w_max,p_max)^{1.961}), including for 0-1 Knapsack.