Source-linked AI summary
Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D
Karl Bringmann, Ariel Kulik, Karol Węgrzycki
TL;DR
The paper addresses the gap between coarse fine-grained bounds for approximating d-Knapsack and precise optimal running-time exponents. It combines slack-based representative solutions with meet-in-the-middle algorithms and derives k-SUM lower bounds. The results nearly determine the 2-Knapsack exponent and establish bicriteria optimality, while leaving fine-grained optimality open.
Problem
Prior approximation schemes and lower bounds for d-Knapsack determine running-time exponents only up to constant factors, leaving their precise optimal exponents unresolved.
Method
The paper combines dynamic-programming generation of representative solutions for slack instances with meet-in-the-middle algorithms and k-SUM-based lower bounds.
Results
For 2-Knapsack, the optimal exponent is 1/(2ε)±O(1), and a (1−ε−δ)-approximation runs in Õ(n^{⌈1/(2ε)−1/2⌉}) while the matching (1−ε) guarantee is conditionally impossible at that exponent.
Takeaways & Limitations
The paper achieves the first more-than-constant-factor characterization of an optimal exponent for a problem admitting a PTAS but no EPTAS and gives a bicriteria-optimal algorithm for 2-Knapsack.
Takeaways & Limitations
Fine-grained optimality remains open for 2-Knapsack, and the paper leaves related goals open for d-Knapsack with d>2.
Abstract
from arXiv · showhide
We revisit the $d$-dimensional Vector Knapsack problem ($d$-Knapsack): Given a $d$-dimensional capacity vector and a set of items, each with a $d$-dimensional weight vector and a profit, the goal is to select a set of items that maximizes the total profit without exceeding the capacity in any dimension. For any $d\ge2$, the best known approximation scheme for $d$-Knapsack runs in time $O(n^{\lceil d/\varepsilon\rceil-d})$ [Caprara, Kellerer, Pferschy, Pisinger '00]. We improve this running time to $\widetilde O_{d,\varepsilon,ρ}(n^{\lceil\frac{d-1}{2\varepsilon}-\frac12+ρ\rceil}+n^d)$ for any $\varepsilon\in(0,1)$ and every parameter $ρ\in(0,1)$. We achieve this speedup by designing the first meet-in-the-middle algorithm for $d$-Knapsack. This requires replacing the LP solver used in prior algorithms by a highly efficient dynamic programming algorithm to generate representative solutions, building on an LP-based structural argument. This is the first improvement in over 25 years, and the first result that improves the exponent by a constant factor. We complement this by a fine-grained lower bound based on $k$-SUM showing that 2-Knapsack requires time $n^{\lceil\frac1{2\varepsilon}-\frac12 \rceil-o(1)}$. This establishes the optimal exponent of 2-Knapsack as $\frac1{2\varepsilon}\pm O(1)$, which is precise up to an additive $O(1)$. To the best of our knowledge, this is the first result that determines the optimal exponent more precisely than up to a factor $O(1)$, for any problem that admits a PTAS but no EPTAS. For the special case of 2-Knapsack we further attain a $(1-\varepsilon-δ)$-approximation in time $\widetilde O_{δ,\varepsilon}(n^{\lceil\frac1{2\varepsilon}-\frac12\rceil})$. This nearly matches our lower bound, as for a slightly better approximation ratio a slightly better running time is impossible -- so our algorithm is bicriteria-optimal.
1 Introduction
The paper develops faster approximation schemes and fine-grained lower bounds for d-Knapsack, nearly determining the optimal exponent for 2-Knapsack. It also establishes bicriteria optimality for 2-Knapsack and leaves finer optimality questions open for higher dimensions.
- 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.
- 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 ε.
- Optimal Running Time Exponent of 2-Knapsack: 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.
- 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.
2 Preliminaries
d-Knapsack maximizes profit by selecting items whose summed d-dimensional weights do not exceed the capacity vector coordinatewise.
- A d-Knapsack instance has d-dimensional capacities and n items with nonnegative profits and d-dimensional weight vectors.
- A solution is feasible when its total weight is at most the capacity in every dimension.
- The objective is to find a feasible subset of maximum total profit.
- Items are indexed by positive integers and sorted by non-increasing profit.
- The algorithms are presented in the RealRAM model and also work in the WordRAM model for machine-word integers.
3 A Simple Improved Algorithm for d-Knapsack
The simple improved algorithm combines slack generation with dynamic programming to obtain a faster approximation scheme for d-Knapsack.
- n^(d−1)/ε · (n/ε)^O(d) is achieved by the warmup algorithm, improving the prior exponent for n ≫ 1/ε ≫ d.
- Slack generation: The Slack-Generating Lemma finds a subset with 1−δ smaller weights in the first d−1 dimensions and bounded profit loss.
- Slack generation: The lemma is proved through an LP with d−1 scaled capacity constraints and at most d−1 fractional variables in a basic optimum.
- 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.
- Replacing prior LP-based extension with dynamic programming reduces the additive loss from d items to d−1 items.
- The resulting algorithm returns a feasible (1−ε)-approximation, and enumerating at most q items yields the stated guarantee.
4 Further Improved Algorithm for d-Knapsack
The further improved algorithm combines representative virtual items with meet-in-the-middle and orthogonal range searching.
- Meet in the middle: Meet-in-the-middle queries combine enumerated item subsets with representative virtual items to produce the approximation.
- Implicit representation: Virtual items represent item sets implicitly, avoiding an additional O(n) factor from explicitly manipulating those sets.
- Implicit representation: A virtual item supports constant-time profit and coordinate-weight access and linear-time recovery of its represented set.
- Representative solutions: The approximation lemma computes representative virtual items for slack instances in time n·(log(n/η)/ε)^O(d).
- Representative solutions: Each representative virtual item can replace a set while preserving feasibility and incurring only a small profit loss.
- Theorem 1.1 gives a (1−ε)-approximation in time Õ_{d,ε,ρ}(n^⌈(d−1)/(2ε)−1/2+ρ⌉ + n^d).
5 A Near-Linear-Time
The two-dimensional algorithm tailors the meet-in-the-middle toolkit to avoid the n^2 term while retaining a near-linear running time.
- Theorem 1.2 uses meet in the middle, slack generation, and approximation by virtual items to avoid quadratic dependence on n.
- Case analysis: The algorithm handles four cases based on the optimal solution’s cardinality and the profits of its leading items.
- Case analysis: For low-profit-leading solutions, slack generation yields a surrogate virtual item representing most of the optimum’s profit.
- Case analysis: For solutions whose first two items carry sufficient profit, meet in the middle finds the optimal cardinality-two solution.
- Algorithm: Algorithm 4 returns a feasible solution by querying orthogonal range structures with residual capacity ranges.
- Guarantee: n·(log(n)/ε)^O(1) is the total running time of Algorithm 4.
A Proof of Corollary 1.4
The proof derives Corollary 1.4 from Theorems 1.1–1.3 by slightly strengthening the approximation parameter and bounding the resulting exponent. It handles separate parameter regimes to obtain the stated running time, with the lower bound inherited directly from Theorem 1.3.
- 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.
- 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.
- 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.
- 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.
- Running time: 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.
- Lower bound: The lower-bound statement follows directly from Theorem 1.3.