Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D

Near-Linear-Time Approximation for 2-Knapsack

• The results improve the previous 2-Knapsack time O(n^{⌈2/ε⌉−2}) for every ε∈(0,2/3).For ε≥2/3, the prior algorithm already achieved optimal linear running time.Source: §1.1 · p. 3

Optimal Running Time Exponent of 2-Knapsack

• For 2-Knapsack, the optimal exponent for a (1−ε)-approximation is 1/(2ε)±O(1), assuming the k-SUM Hypothesis.More precisely, it is ⌈1/(2ε)−1/2⌉ up to arbitrarily small error and an arbitrarily small change in ε.Source: §1.1 · p. 3, §1.3 · p. 6
• 2-Knapsack has a (1−ε−δ)-approximation in time Õ(n^{⌈1/(2ε)−1/2⌉}), while a (1−ε)-approximation requires a strictly larger exponent under the k-SUM Hypothesis.This yields bicriteria-optimal running time: slightly better approximation cannot be obtained with a slightly smaller exponent.Source: §1.1 · p. 3, §1.2 · p. 5

Improved Algorithm for d-Knapsack

• The algorithm combines slack-generating representative solutions with meet-in-the-middle techniques.Representative solutions are generated efficiently using dynamic programming after discretizing capacity vectors, enabling low-profit items to be incorporated into meet-in-the-middle computation.Source: §1.3 · pp. 7–8

• A d-Knapsack instance has d-dimensional capacities and n items with nonnegative profits and d-dimensional weight vectors.Source: §2 · p. 9
• A solution is feasible when its total weight is at most the capacity in every dimension.Source: §2 · p. 9
• The objective is to find a feasible subset of maximum total profit.Source: §2 · p. 9
• Items are indexed by positive integers and sorted by non-increasing profit.Source: §2 · p. 9
• The algorithms are presented in the RealRAM model and also work in the WordRAM model for machine-word integers.Source: §2 · p. 9

• n^(d−1)/ε · (n/ε)^O(d) is achieved by the warmup algorithm, improving the prior exponent for n ≫ 1/ε ≫ d.Source: §3 · p. 9

Slack generation

• The Slack-Generating Lemma finds a subset with 1−δ smaller weights in the first d−1 dimensions and bounded profit loss.Source: §3.1 · p. 10
• The lemma is proved through an LP with d−1 scaled capacity constraints and at most d−1 fractional variables in a basic optimum.Source: §3.1 · p. 10

Instances with slack

• Dynamic programming rounds profits down and the first d−1 weights up, then maximizes rounded profit subject to all rounded capacity constraints.Source: §3.2 · pp. 11–13

• Replacing prior LP-based extension with dynamic programming reduces the additive loss from d items to d−1 items.Source: §3.3 · pp. 13–14
• The resulting algorithm returns a feasible (1−ε)-approximation, and enumerating at most q items yields the stated guarantee.Source: §3.3 · p. 14

Meet in the middle

• Meet-in-the-middle queries combine enumerated item subsets with representative virtual items to produce the approximation.Source: §4 · p. 15, §4.4 · p. 23

Implicit representation

• Virtual items represent item sets implicitly, avoiding an additional O(n) factor from explicitly manipulating those sets.Source: §4.1 · p. 15
• A virtual item supports constant-time profit and coordinate-weight access and linear-time recovery of its represented set.Source: §4.1 · p. 15

Representative solutions

• The approximation lemma computes representative virtual items for slack instances in time n·(log(n/η)/ε)^O(d).Source: §4.2 · pp. 16–17
• Each representative virtual item can replace a set while preserving feasibility and incurring only a small profit loss.Source: §4.2 · p. 17

• Theorem 1.1 gives a (1−ε)-approximation in time Õ_{d,ε,ρ}(n^⌈(d−1)/(2ε)−1/2+ρ⌉ + n^d).Source: §4.4 · p. 24

• Theorem 1.2 uses meet in the middle, slack generation, and approximation by virtual items to avoid quadratic dependence on n.Source: -Approximation for 2-Knapsack · p. 31

Case analysis

• The algorithm handles four cases based on the optimal solution’s cardinality and the profits of its leading items.Source: -Approximation for 2-Knapsack · pp. 31, 34
• For low-profit-leading solutions, slack generation yields a surrogate virtual item representing most of the optimum’s profit.Source: -Approximation for 2-Knapsack · p. 31
• For solutions whose first two items carry sufficient profit, meet in the middle finds the optimal cardinality-two solution.Source: -Approximation for 2-Knapsack · p. 31

Algorithm

• Algorithm 4 returns a feasible solution by querying orthogonal range structures with residual capacity ranges.Source: -Approximation for 2-Knapsack · p. 32

Guarantee

• n·(log(n)/ε)^O(1) is the total running time of Algorithm 4.Source: -Approximation for 2-Knapsack · pp. 35–36

Parameter choice

• Setting δ′ := min{δ, ε^2}, ε′ := ε + δ′, and ρ := δ′/(4ε^2) enables Theorem 1.1 to compute a (1 − ε′)-approximation.When ε′ ≥ 1, the empty set gives the trivial ratio; otherwise Theorem 1.1 applies.Source: A Proof of Corollary 1.4 · p. 39

Exponent bound

• The inequality 1/(1 + x) ≤ 1 − x/2 bounds the adjusted exponent by 1/(2ε) − 1/2.The choice of ρ is used in this exponent calculation.Source: A Proof of Corollary 1.4 · p. 39

Approximation guarantee

• Because 1 − ε′ ≥ 1 − ε − δ, the resulting algorithm achieves a (1 − ε − δ)-approximation.This transfers the guarantee from the strengthened parameter ε′ to the corollary’s target ratio.Source: A Proof of Corollary 1.4 · p. 39

Running time

• For ε below the stated threshold, Theorem 1.1 yields the target approximation in time eO(n^⌈1/(2ε)−1/2⌉).The proof uses ⌈1/(2ε) − 1/2⌉ ≥ 2 in this regime.Source: A Proof of Corollary 1.4 · p. 39
• For the complementary regime, Theorem 1.2 supplies a sufficient approximation in eO(n), which is bounded by the same target time.Since ε < 1, the target exponent is at least 1.Source: A Proof of Corollary 1.4 · p. 39

Lower bound

• The lower-bound statement follows directly from Theorem 1.3.Source: A Proof of Corollary 1.4 · p. 39