Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing

1.1 Our results

• eO(n + t√pmax) improves the prior eO(n + t pmax) bound by a factor √pmax.Source: §1.1 · pp. 2–3
• Other randomized bounds are eO(n + OPT√wmax), eO(n + (nwmaxpmax)^(1/3)t^(2/3)), and eO(n + (nwmaxpmax)^(1/3)OPT^(2/3)); weight and profit parameters can be exchanged.Source: §1.1 · p. 3
• Polynomial-factor improvements in any Theorems 1–4 running time would yield an O(n^(2-epsilon))-time algorithm for bounded min-plus convolution verification, supporting a near-optimality barrier.The reduction covers improvements in n, wmax, pmax, t, or OPT.Source: §1.1 · pp. 3–4

1.2 Technical overview

• The algorithms randomly split items into 2q groups, compute per-group profit sequences, then combine them in a tree using max-plus convolution.Source: §1.2 · p. 4

Rectangular Monotone Max-Plus Convolution

• The convolution tool allows monotone sequences with entries bounded by arbitrary M, and a recurrence removes the requirement that both inputs be monotone.Source: Rectangular Monotone Max-Plus… · pp. 4–5

Balancing

• A randomized reduction solves O(wmax) consecutive capacities or O(pmax) consecutive profits on a reduced instance balanced so t/wmax = Θ(OPT/pmax).The reduced instance consists of a subset of the original items.Source: Balancing · p. 5

2 Preliminaries

• Max-plus convolution combines entries whose indices sum to k by taking the maximum of their summed values; bounded monotone convolution restricts both input sequences to monotone non-negative entries bounded by M.The rectangular case allows M to differ from the sequence length; min-plus convolution is equivalent by negating the inputs and output.Source: §2 · p. 6
• Knapsack selects items of weights wi and profits pi to maximize total profit subject to capacity t, and nontrivial instances may assume wmax ≤ t and t < nwmax.If t ≥ nwmax, all items fit and the instance is trivial.Source: §2 · p. 6
• Bellman’s dynamic program computes PI[0 . . . k] in O(|I| · k) time, while PI is monotone non-decreasing and its breakpoints define Pareto optima.A Pareto optimum has no other solution of no greater weight and greater profit.Source: §2 · p. 7
• The sequence PI[0 . . . t; 0 . . . v] can be computed in randomized time eO(n + t√v), with correctness holding with high probability.This rectangular sequence computation is stated for a Knapsack instance and v ∈ N.Source: §2 · p. 7
• A greedy fractional relaxation yields an estimate of OPT in eO(n) time satisfying OPT ≤ OPT_est ≤ OPT + pmax.The estimate is also bounded above by n · pmax.Source: §2 · p. 7
• The paper uses eO notation to hide polylogarithmic factors, and its randomized subroutines can be boosted to success probability 1 − 1/n^10 at constant-factor time overhead.The stated baseline success probability is at least 1 − 1/n.Source: §2 · p. 8

3 Knapsack algorithm for balanced instances

• Under the balancedness assumption, randomized algorithms compute the target sequence in eO(n + t√pmax) time or eO(n + (nwmaxpmax)^(1/3) · t^(2/3)) time.The bounds are given in Lemmas 15 and 16, respectively.Source: §3 · p. 8
• Algorithm 1 randomly partitions items, computes restricted subarrays, and combines them by max-plus convolution using rectangular bounded monotone convolution.The sequences are monotone non-decreasing, and the algorithm restricts computation to small ranges of indices and values.Source: §3 · pp. 8–9

3.1.1 Correctness of Algorithm 1

• With high probability, Algorithm 1’s output on the specified target ranges equals the corresponding subsequence of the original Pareto sequence.The success probability can be boosted to any polynomial by repetition and taking entry-wise maxima.Source: §3.1.1 · p. 12
• For n^3 ≥ 2p_max, C_1^0[T; P] equals PI[T; P] with probability at least 1 − 2p_max/n^4 ≥ 1 − 1/n, from the bound 1 − 2p_max√n/n^5.When n^3 ≤ 2p_max, Bellman’s dynamic program computes the profit sequence in time O(n · t) = O(t√p_max).Source: §3.1.1 · p. 13

3.1.2 Running time of Algorithm 1

• At each level, Algorithm 1 combines bounded monotone sequences via max-plus convolution, using balancedness to bound the combination step by eO(t*p_max^1/2).The sequences have lengths tied to Δw/2^ℓ and value ranges tied to Δp/2^ℓ.Source: §3.1.2 · pp. 13–14
• Algorithm 1 runs in eO(n + t*p_max^1/2) time.The base-case and combination steps are each bounded by eO(t*p_max^1/2), in addition to the input-size term.Source: §3.1.2 · pp. 13–14

O(n + (nwmaxpmax)1/3t2/3)-time algorithm

• eO(n + (nwmaxpmax)1/3 · t2/3) time suffices for the algorithm in this section.The proof modifies Algorithm 1 to achieve this bound.Source: O(n + (nwmaxpmax)1/3t2/3)-time algorithm · p. 14
• eO(n√t · wmax + nℓ) time computes the profit sequence for capacities t − ℓ through t + ℓ with probability at least 1 − 1/n.The randomized procedure replaces the base case of Algorithm 1.Source: O(n + (nwmaxpmax)1/3t2/3)-time algorithm · p. 14
• The algorithm computes only a subarray of the dynamic-programming table, of length Δ = eO(ℓ + √t · wmax), centered near the expected weight of the processed prefix.Items are first randomly permuted.Source: O(n + (nwmaxpmax)1/3t2/3)-time algorithm · p. 14
• A stronger Hoeffding-style bound for samples without replacement handles varying lower and upper bounds, unlike the weaker variant used by He and Xu [14].The paper identifies this refinement as necessary for the improved running time.Source: O(n + (nwmaxpmax)1/3t2/3)-time algorithm · p. 15

3.3 Reconstructing an optimal solution

• An optimal item set can be reconstructed by recursively tracing witnesses through the convolution sequences, with total tracing time eO(t).The reconstruction adds no extra overhead for the arrays computed using Theorem 12.Source: §3.3 · p. 17

4 Balancing instances

• Randomized eO(n + min{wmax√pmax, pmax√wmax}) time reduces a general instance to one satisfying t/wmax = Θ(OPT/pmax).The reduced instance uses a subset of the original items, and its parameters are no larger than the original's.Source: §4 · pp. 17, 20
• The reduction bounds the good-item and bad-item differences between the maximum prefix solution and an optimum, leaving the medium items as the main reduced instance.It then solves bounded ranges for the bad and good items and combines the resulting solutions with two max-plus convolutions.Source: §4 · pp. 18–20
• The medium items have profit-to-weight ratios within a factor of 4, and their reduced instance uses capacity t′ = w(P ∩ M).The section defines the medium group relative to the profit-to-weight ratio of the last item in the maximum prefix solution.Source: §4 · pp. 18–19
• Combining the reduction with balanced-instance algorithms gives general-instance running times eO(n + t√pmax) and eO(n + OPT√wmax).The reduction's cost does not exceed these algorithm bounds under wmax ≤ t and pmax ≤ OPT.Source: §4 · p. 20

5 Reduction from bounded min-plus convolution verification

• A polynomial-factor speedup over any of Theorems 1–4 in any of n, wmax, pmax, t, or OPT would imply an O(n2−ε)-time algorithm for Bounded Min-Plus Convolution Verification.This is the conditional lower-bound result stated in Theorem 6.Source: §5 · p. 20
• Adding index-dependent offsets makes the input sequences non-decreasing while preserving the verification condition.The reduction moves from entries bounded by n to monotone sequences with entries bounded by O(n2).Source: §5 · p. 21
• The Knapsack construction encodes a failed verification inequality as a feasible choice of one A-item, one B-item, and one C-item with profit above 112n2.The constructed instance has 4n − 1 items and capacity 35n.Source: §5 · p. 21
• For instances with wmax = O(n), pmax = O(n2), and t = O(n), a faster-than-O(t√pmax) or faster-than-O((nwmaxpmax)1/3t2/3) algorithm would be truly subquadratic.The analogous instance with indices and values swapped has wmax = O(n2), pmax = O(n), t = O(n2), and OPT = O(n), giving the corresponding lower-bound implication for the symmetric running times.Source: §5 · p. 22

6 From one monotone to two monotone sequences

• An algorithm for two monotone non-decreasing sequences yields one for a monotone sequence and an arbitrary sequence, with T1(n, M) ≤ 2T1(n/2, M) + O(T2(n, M)).The section states the same result for non-increasing sequences and for min-plus convolution.Source: §6 · p. 22
• If T2(n, M) = Θ(n^αf(M)), the recurrence gives T1(n, M) = O(T2(n, M)) for α > 1 and O(T2(n, M) log n) for α = 1.The paper presents the reduction as a side result because its Knapsack algorithms already produce instances with both sequences monotone.Source: §6 · p. 22
• For the first half of the output, replacing the arbitrary input by its prefix maxima preserves the convolution values when the other input is monotone.This provides the reduction step used by the full-sequence algorithm.Source: §6 · p. 23
• For the full output, the algorithm splits both sequences in half, uses prefix maxima in two subproblems, and recursively computes the other two subproblems.The four resulting sequences are combined to obtain the full convolution.Source: §6 · pp. 23–24

A Additional Knapsack algorithms

• The weight sequence can also be computed by dynamic programming in O(|I| · k) time for indices 0 through k.The recurrence takes the minimum of the previous value and the weight of item i plus the value at profit index k − pi.Source: A Additional Knapsack algorithms · pp. 27–28
• The weight sequence is monotone, and the appendix adapts bounded monotone min-plus convolution to compute a subarray of it.Theorem 32 computes WI[V; T] with high probability; its stated running-time expression is incomplete in the passage.Source: A Additional Knapsack algorithms · p. 28
• Any knapsack instance can be reduced to a balanced instance, where t/wmax = Θ(OPT/pmax), enabling these additional running-time bounds.The appendix combines this reduction with Lemmas 34 and 35.Source: A Additional Knapsack algorithms · p. 28
• For balanced instances, the weight-sequence subarray can be computed by a randomized algorithm in time eO(n + OPT√wmax).Balanced means t/wmax = Θ(OPT/pmax).Source: A Additional Knapsack algorithms · p. 28
• For balanced instances, a randomized algorithm computes the weight-sequence subarray in time eO(n + (nwmaxpmax)^(1/3) · OPT^(2/3)).Combining this balanced-instance result with the reduction yields Theorem 4.Source: A Additional Knapsack algorithms · p. 28

A.1.1 Correctness of Algorithm 3

• The arrays Cℓ_j[Pℓ; Wℓ] are monotone non-decreasing, so their min-plus convolutions preserve monotonicity through the combination tree.This monotonicity justifies using the min-plus convolution algorithm in the combination step.Source: §3.1.1 · p. 10, §A.1.1 · p. 30
• Every break point k of WI has another break point in [k − pmax, k), linking neighboring changes in the weight sequence to the maximum item profit.The proof removes one item from a Pareto-optimal solution at k; the removed item's profit is at most pmax.Source: §A.1.1 · p. 31
• With high probability, Algorithm 3's computed subarray equals WI[P; T], establishing correctness on the target profit and weight ranges.The success probability can be boosted by repeating the algorithm and taking the entry-wise maximum of computed arrays.Source: §A.1.1 · p. 31

A.1.2 Running time of Algorithm 3

• At each combination level, min-plus convolution combines monotone sequences whose value ranges shrink with the level.The analysis applies Theorem 7 to ranges of lengths at most Δp/2ℓ and Δw/2ℓ, then sums the resulting costs across levels.Source: §A.1.2 · pp. 31–32
• Algorithm 3 runs in time eO(n + OPT√wmax).The bound covers the base case and all combination steps.Source: §A.1.2 · p. 32

O(n + (nwmaxpmax)1/3OPT2/3)-time Algorithm

• For balanced instances, a randomized algorithm computes the specified weight-sequence subarray in time eO(n + (nwmaxpmax)^(1/3) · OPT^(2/3)).The result, combined with the reduction to balanced instances, yields Theorem 4.Source: O(n + (nwmaxpmax)1/3OPT2/3)-time… · p. 32
• The modified algorithm uses a randomized procedure to compute WI on a local interval around a target profit in time eO(n√v · pmax + nℓ).The procedure is stated to be correct with probability at least 1 − 1/n.Source: O(n + (nwmaxpmax)1/3OPT2/3)-time… · p. 33
• The algorithm adapts Algorithm 3 by replacing its base computation with the local weight-sequence procedure, while retaining the combination approach.The paper derives the local procedure from the idea of He and Xu [14].Source: O(n + (nwmaxpmax)1/3OPT2/3)-time… · pp. 32, 34

• Theorem 7 handles min- or max-plus convolution of two same-direction monotone sequences of length at most n, with entries in {0, …, M}, using a randomized algorithm correct with high probability.Source: B Rectangular Bounded Monotone… · p. 34
• The proof adapts Chi et al. [11, Theorem 1.5] from increasing sequences with M = Θ(n) to non-decreasing or non-increasing sequences and arbitrary M.Source: B Rectangular Bounded Monotone… · p. 35
• For arbitrary M, the running-time analysis replaces the original terms with Õ(nM^α + nM^(1−α) + M^(2−2α)).Source: B Rectangular Bounded Monotone… · p. 35

B.1 Algorithm of Theorem 43

• A sampled prime partitions each input into three residue classes, yielding nine shifted convolution pairs that preserve the original minimum while meeting the residue assumption.The assumption requires residues at most p/3 or infinity, with monotonicity except at infinity entries.Source: §B.1 · p. 36

B.1.1 Computing ˜

• The quotient component uses constant intervals of the transformed inputs; pairwise interval updates compute the quotient convolution in Õ(M^(2−2α)) time.There are O(M^(1−α)) intervals per sequence, and a segment tree performs each update.Source: §B.1.1 · p. 36

B.1.2 Computing C∗

• The residue component is built recursively from coarse to fine levels, using FFT polynomial products and offsets in [−10, 10] to filter candidate sums.At the final level, the construction recovers C mod p for finite entries.Source: §B.1.2 · pp. 37–39

• At each recursive level, a true minimizing pair appears among the candidates, and taking the minimum candidate yields a valid C(ℓ)[k].The base case is the zero sequence; the induction uses the bounded-offset lemma and the construction of the candidate set.Source: §B.2 · pp. 40–41

• At level ℓ, there are O(nM/2^ℓ) segments, while sampling a prime bounds the expected number retained in the filtering sets.The analysis uses this bound to control the recursive work.Source: §B.3 · pp. 41–42
• Õ(M^(2−2α) + nM^(1−α) + nM^α) expected time is obtained by combining quotient, initialization, and recursive-level costs; α = 1/2 gives the stated bound.Source: §B.3 · p. 41

C Using rectangular convolution in Bringmann–Cassis algorithm

• The sequences PI[0...t; 0...v] and WI[0...v; 0...t] can be computed in times eO(n + t√v) and eO(n + v√t), respectively.Source: C Using rectangular convolution in… · p. 42

C.1 Computing PI[0 . . . t; 0 . . . v]

• Items are partitioned into O(log t log v) dyadic weight-profit groups, whose sequences are combined by max-plus convolution in eO(T(t, v)) time.The partition takes linear time, and the sequence-combination step also takes eO(T(t, v)) time.Source: §C.1 · p. 43, Merging the sequences Pu · p. 44

Computing Pu

• Randomly splitting a group into z subgroups bounds each fixed solution to O(log z) selected items per subgroup with probability at least 1−1/poly(z).Color coding and repeated trials compute the subgroup sequences; their total computation takes eO(T(t, v)) time.Source: §C.1 · p. 43, Computing Pu · pp. 43–44

Merging the sequences Pu

• The subgroup sequences are merged in a tree-like fashion, with the merging step taking eO(T(t, v)) time.There are ⌈log z⌉ levels of max-plus convolution.Source: Merging the sequences Pu · p. 44

C.2 Computing WI[0 . . . v; 0 . . . t]

• The weight-sequence computation uses min-plus convolution with the dimensions swapped, computing WI[0...v; 0...t] in eO(T(v, t)) time.The construction is nearly identical to the profit-sequence method, with min-plus replacing max-plus convolution.Source: §C.2 · pp. 44–45