CS Paper Radar

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

Karl Bringmann, Ariel Kulik, Karol Węgrzycki

cs.DS ·submitted 2026-08-27 18:31 UTC · v1
theory

Abstract

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.

Comment
Abstract shortened to fit ArXiV requirements

Closest papers

Nearest neighbours by meaning across the whole index.

Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time

cs.DS ·2026-10-09 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.69
Abstract

We give an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for multidimensional subset sum on an explicitly listed multiset of $n$ vectors in $[-N,N]^d$, for every fixed $d$ and $\varepsilon>0$. This directly implies an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for feasibility test of integer programming. Prior to our work, the best-known algorithm has a running time of $O_{d}(n+N^{O(d^2)})$ [Eisenbrand, Weismantel'19]. Specifically, if $d=1$, our algorithm runs in $O_{\varepsilon}(n+N^{1+\varepsilon})$-time for the standard subset sum problem, which is near-linear in the largest input integer. Prior to our work, subset sum can be solved in time near-linear in the target $t$ [Bringmann'17], or near-linear in the mixed parameter $\sqrt{Nt}$ [Chen, Lian, Mao, Zhang'24]. It is a fundamental open problem whether the algorithm can be made near-linear in $N$, which is settled affirmatively in this paper up to an arbitrary small $N^{\varepsilon}$ term.

0.26

Inclusion-wise extremal knapsack problems are (mostly) hard to approximate

cs.DS math.OC ·2026-10-13 ·Fabio Ciccarelli, Fabio Furini, Ulrich Pferschy, Elena Rener
similarity 0.67
Abstract

We study two inclusion-wise extremal variants of the 0-1 Knapsack Problem (KP). Given $n$ items with integer weights and nonnegative costs or profits, the Minimum-Cost Maximal Knapsack Packing Problem seeks a minimum-cost packing for capacity $c$ to which no item can be added, while the Maximum-Profit Minimal Knapsack Cover Problem seeks a maximum-profit cover for threshold $d$ from which no item can be removed. Both problems are weakly $\mathrm{NP}$-hard and pseudo-polynomially solvable, as is the classical KP, but their approximability is fundamentally different: unless $\mathrm{P}=\mathrm{NP}$, with positive values neither problem admits a polynomial-time $2^{p(n)}$-approximation for any polynomial $p$; allowing zero values rules out every multiplicative factor. Even with unit costs for packing and unit profits for covering, neither admits an $n^{1-\varepsilon}$-approximation for any fixed $\varepsilon>0$, whereas a trivial $n$-approximation exists. We identify restrictions that restore approximability. If every item weighs at least a fixed fraction of the capacity, respectively of the threshold, both problems can be solved exactly in polynomial time. For the cover problem, if each weight $w_i$ satisfies $w_i-1\geδ(d-1)$, we give an approximation scheme for arbitrary profits whose running time is polynomial in $n$, $1/\varepsilon$, and $1/δ$. If values equal weights, a fully polynomial-time approximation scheme (FPTAS) was already known for the packing problem; we give an FPTAS for the cover problem, improving on the previously known factor $2$. If value-to-weight ratios differ by at most a factor $κ$, we obtain a $(1+\varepsilon)κ$-approximation for both problems.

0.10

Faster Deterministic Approximation for Counting Knapsack

cs.DS ·2026-10-10 ·Ce Jin, Jaewoo Park, Barna Saha
top venue similarity 0.66
Abstract · To appear in SODA 2027. 32 pages

Given $n$ nonnegative integer weights $w_1, \ldots, w_n$ and an integer knapsack capacity $T$, the $\#$Knapsack problem asks to count the number of subsets $I \subseteq \{1, 2, \dots, n\}$ such that $\sum_{i \in I} w_i \le T$. A long line of research has been devoted to designing faster $(1 \pm \varepsilon)$-approximation algorithms for this \#P-hard problem. Until very recently, the best-known time complexity was $\tilde{O}\bigl(n^{2.5}/\mathrm{poly}(\varepsilon)\bigr)$, achieved by the randomized algorithm of [Dyer, STOC 2003] and the deterministic algorithm of [Gawrychowski, Markin, and Weimann, ICALP 2018]. The recent work by [Feng and Jin, SODA 2025] improved the randomized complexity to $\tilde{O}\bigl(n^{1.5}/\mathrm{poly}(\varepsilon)\bigr)$, leaving open the question whether this $n^{2.5}$ barrier could also be broken by a \emph{deterministic} algorithm. In this work, we answer this question in the affirmative by presenting a deterministic $(1 + \varepsilon)$-approximation algorithm for \#Knapsack in $\tilde{O}\bigl(n^{2.4}/\mathrm{poly}(\varepsilon)\bigr)$ time. Our key technical innovation is to deterministically simulate the balancing technique, which was previously used in the literature of knapsack-type problems via random partitions and seemed to require randomization.

0.51

Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means

cs.CG cs.CCcs.DSstat.ML ·2026-11-11 ·Karthik C. S., Dor Minzer
theory similarity 0.65
Abstract

In the Euclidean $k$-means problem, we are given a set of $n$ points in $\mathbb{R}^d$, and the goal is to find $k$ representative points in space so as to minimize the sum of the squared distances from each point to its closest representative. Algorithmically, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] obtain a $(1+\varepsilon)$-approximation for high-dimensional Euclidean $k$-means in time $2^{(k/\varepsilon)^{O(1)}} \cdot dn^{O(1)}$, which was subsequently improved to $2^{\tilde{O}(k/\varepsilon)} + O(ndk)$ by Feldman, Monemizadeh, and Sohler [SoCG'07]. On the lower-bound side, a recent work of Cohen-Addad, Karthik, Saulpic, and Schwiegelshohn [SoCG'26] proposed the Exponential Time for Expanders Hypothesis (XXH), which asserts exponential-time hardness for $(1+\varepsilon)$-approximating Vertex Cover on vertex expanders, and used it to prove nearly matching running time lower bound whenever $k=\tildeω(1/\varepsilon)$. We observe that XXH does not hold in the parameter regime needed for the above result, and show how to repair their reduction under a more standard assumption. More precisely, we show that assuming the Almost Exponential Time Hypothesis for 3-SAT (Almost ETH), for every constant $β\in(0,1)$, Euclidean $k$-means in $\mathbb{R}^d$ has no $(1+\varepsilon)$-approximation algorithm running in time $2^{(k/\varepsilon)^{1-β}}\text{poly}(n,d)$, whenever $k=\tildeω(1/\varepsilon)$. By modifying the construction, we also obtain a similar result for approximating the Euclidean $k$-median problem.

0.12

Bounded Knapsack in Truly Subquadratic Time

cs.DS cs.CG ·2026-11-11 ·Huanyi Zhou
similarity 0.64
Abstract · 66 pages, 5 figures

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.

0.52

A Combinatorial $(1/2-\varepsilon)$-Approximation for $k$-Submodular Maximization under Multiple Knapsacks

cs.DS ·2026-10-17 ·Siyuan Chen, Suixiang Gao, Zheyu Jiang, Wenguo Yang
similarity 0.61
Abstract · 23 pages

We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2 \). The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al. \cite{chen2026}: it samples from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these gains. Extending their single-knapsack Bellman analysis, we construct a common resource potential and associated resource weights, with potential losses charged to greedy gains. Since these weights depend on the unknown optimum, we discretize their defining coefficients and enumerate monotone guesses over phases determined by resource consumption. This yields an algorithm using at most $\mathcal{A}(d,\varepsilon)(nk+1)^{H+2}$ value queries, where $n$ is the number of elements, $\mathcal{A}(d,\varepsilon)$ depends only on $d$ and $\varepsilon$, and $H=O(d \log(2d) / \varepsilon^2)$. The approximation ratio can be made arbitrarily close to the optimal oracle threshold for \( k=2 \) and is asymptotically tight as \(k \to \infty\).

0.21

On the Largest Cardinality Subset Sum

cs.DS ·2026-10-21 ·Deepak Bhati, Anubhav Dhar, Pranjal Dutta, Mahesh Sreekumar Rajasree, Karol Węgrzycki
similarity 0.61
Abstract · Submitted to STACS 2027

We study Largest Cardinality Subset Sum (LCSS): given $n$ nonnegative integers and a target $t$, compute a subset summing to $t$ with maximum cardinality. We also consider its all-targets version (ATLCSS), which asks for this maximum for every sum $s\in\{1,\ldots,t\}$. The LCSS problem sits squarely between the subset sum and the knapsack problem. A straightforward dynamic-programming algorithm runs in time $O(nt)$ and solves ATLCSS, and using Jin and Bringmann (both in STOC 2024, independent work) $0$-$1$ knapsack results we achieve a $\widetilde{O}(n + a_{\max}^2)$-time deterministic algorithm for LCSS. Our main result is a randomized $\widetilde{O}(n+\sqrt{n}\,t)$-time algorithm for LCSS. Then, we complement this result with a randomized $\widetilde{O}(n+t^{3/2})$-time algorithm for ATLCSS. Together, our two algorithms give a $\widetilde{O}(n+t\min\{\sqrt{n},\sqrt{t}\})$-time algorithm for LCSS. As an application of ATLCSS, we solve the search version of Projection Subset Sum, introduced by Dutta and Rajasree (SYNSAC 2023), in $\widetilde{O}(n+t^{3/2})$ time for every fixed $\ell_p$ norm with $p\geq 1$. For $\ell_1$, we obtain $\widetilde{O}(n+t)$ time, removing the unique-representation assumption required by their algorithm. Both algorithms output an optimal modified vector and a witnessing subset.

0.19

A Note on Truly Subquadratic Time FPTAS for Knapsack

cs.DS ·2026-11-17 ·Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
similarity 0.61
Abstract

We show that an $\widetilde{O}(m^ρ)$-time algorithm for integer $(\min,+)$-convolution, where $1<ρ<2$, gives a randomized fully polynomial-time approximation scheme for $0$--$1$ Knapsack running in $\widetilde{O}(n+(1/ε)^{1+ρ/2})$ time. The algorithm returns a feasible solution whose profit is at least the optimum divided by $1+ε$, with high probability. We use the all-capacities proximity decomposition of Chen, Lian, Mao, and Zhang. Its two quadratic computations are replaced by blocked computation of requested prefix and suffix functions, and exact computation within groups sharing one of Chan's profit grids. Thus the approximation scheme retains half of the saving in the convolution exponent. Wang's weighted-cache 3SUM bound, transferred to witnessed integer convolution by Zhou, gives the numerical bound $\widetilde{O}(n+(1/ε)^{1.981})$.

0.26