CS Paper Radar

Simpler Algorithms for Knapsack, Subset Sum, and Min-Plus Convolution

Trevor Vaughn

cs.DS ·submitted 2026-09-27 04:11 UTC · v1

Abstract

We simplify algorithms for Knapsack, output-sensitive Subset Sum, and near-convex min-plus convolution. For bounded Knapsack, we give a deterministic algorithm using $O(N+W^2\log^3(W+2))$ arithmetic and comparison operations, where $W$ is the maximum item weight and $N$ counts input records with binary-encoded multiplicities. Following Bringmann's approach, we partition the items and bound the weight added or removed within each part when correcting a greedy solution to an optimum. These bounds keep the dynamic-programming tables small. The same analysis gives the corresponding bound with maximum profit in place of weight. For multiple-choice Knapsack, we give a randomized $\widetilde O(N+w^2\min\{r,w\})$ algorithm, where $N$ counts alternatives, $r$ counts classes, and $w$ is the maximum within-class weight range. Randomly grouping classes exploits cancellation between positive and negative weight changes. For Subset Sum of $n$ nonnegative integer vectors in any fixed dimension $d$, we obtain expected time $\widetilde O(n+s\sqrt n)$, where $s$ counts attainable sums in the target box. With high probability, all sums are returned within the same bound. This improves the $\widetilde O(n+s n^{d/(d+1)})$ bound of Bringmann, Fischer, and Nakos for $d>1$. The key step computes a sumset inside a box without generating the potentially much larger unrestricted sumset. Finally, we simplify the $\widetilde O(N(D+1))$ algorithm for min-plus convolution of integer arrays of total length $N$, where $D$ is the sum of their maximum deviations above convex arrays. The deviations can change the minimizing pairs substantially, but restrict relevant candidate values to short intervals.

Closest papers

Nearest neighbours by meaning across the whole index.

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.71
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

Multiple-Choice Knapsack with Small Items

cs.DS ·2026-11-11 ·Jakub Pawlewicz
published similarity 0.70
Abstract

The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class. Besides the standard dynamic program running in time $\mathcal{O}(nc)$, where $n$ is the total number of items and $c$ is the knapsack capacity, no other pseudopolynomial-time algorithm is currently known. We present an $\mathcal{O}(n+w_{\max}^4)$-time algorithm, where $w_{\max}=\max_i (w_{in_i}-w_{i1})$ is the maximum weight range within a class.

0.58

Bounded Knapsack in Truly Subquadratic Time

cs.DS cs.CG ·2026-11-11 ·Huanyi Zhou
similarity 0.69
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 PTAS for Non-Adaptive Stochastic Top-$k$ Sum under General Combinatorial Constraints

cs.DS cs.CC ·2026-09-03 ·Yu Liu
similarity 0.68
Abstract · Expanded the topk minimization problem with covering dual, as my thesis paper did

We study non-adaptive selection of a feasible set $S$ that maximizes the expected sum of the $k$ largest realized values among independent nonnegative discrete random variables. The same objective arises in team hiring and as VCG welfare in an $\ell$-unit auction. The main setting is a fixed-dimensional nonnegative packing family, whose natural LP has $d=O(1)$ packing inequalities with binary coefficients. We give a PTAS for every $k\ge 1$ on every such family, including binary one- and two-dimensional knapsack, by approximating the occupancy functional $p\mapsto\mathbb{E}[\min(k,N(p))]$ and realizing the resulting signatures in the packing LP. As a generic guarantee the scheme is essentially optimal: there is no FPTAS that works for every such $\mathcal{F}$ unless $P=NP$, and no EPTAS unless $W[1]=FPT$. An incomparable sufficient condition is a query-weight exact-sum oracle (DAG paths, matchings), which likewise yields a PTAS for every $k$. The same signatures give a PTAS for $\min_{S\in\mathcal{F}}\mathbb{E}[\mathrm{Top}_k(S)]$ on every fixed-$d$ covering family; two-dimensional covering knapsack rules out a generic FPTAS on that class.

0.31

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.67
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

A Note on Truly Subquadratic Time FPTAS for Knapsack

cs.DS ·2026-11-17 ·Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
similarity 0.66
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.17

Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint

cs.DS ·2026-09-22 ·Zihui Liu, Zhijie Zhang
similarity 0.65
Abstract · ISAAC 2026

Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motivated by large-scale applications where query efficiency is paramount, we study non-monotone SMK and focus on deterministic algorithms with linear query complexity. Prior deterministic linear-query algorithms achieve at best a $1/5-\varepsilon$ approximation, falling short of the $1/4-\varepsilon$ ratio attainable by randomized algorithms. We close this gap by presenting a deterministic $(1/4-\varepsilon)$-approximation with $O(n\log^2(1/\varepsilon)/\varepsilon^2)$ queries. Our approach partitions the analysis based on the cost of the largest optimal element $r$: when the cost of $r$ is moderate, we refine the threshold-twin-greedy framework via residual-budget enumeration to tighten the analysis; when the cost of $r$ is large, we reduce the problem to bicriteria submodular maximization. As a secondary contribution, we obtain a $(1/2-\varepsilon, O(1/\varepsilon))$-bicriteria approximation with $O(n\log(1/\varepsilon)/\varepsilon^2)$ queries, improving over the previous $O(n^2/\varepsilon)$ query bound.

0.37

Breaking the 1/3 Barrier for constrained $\boldsymbol{k}$-Submodular Maximization: A Proportional Top-2 Randomized Framework

cs.DS ·2026-09-14 ·Siyuan Chen, Shengminjie Chen, Suixiang Gao, Zheyu Jiang, Chenhao Wang +1 more
similarity 0.64
Abstract

$k$-submodularity generalizes submodularity by allowing each selected element to be assigned one of $k$ labels. We study the maximization of a non-monotone $k$-submodular function, where $k\ge2$, under matroid and knapsack constraints. We develop a proportional top-2 randomized framework that achieves an approximation ratio of $\sqrt2-1\approx0.4142$ under either constraint, breaking the previous $1/3$ barrier. Once an element is selected, its label is chosen from the two labels with the largest marginal gains, with probabilities proportional to their positive parts. The analysis separates replacement, pure-addition, and residual-deletion losses, and proves a sharp local loss certificate for this rule. We then give a Bellman analysis using the same local certificate. It gives a $1/2$-approximation under a cardinality constraint and strengthens the knapsack guarantee to $1/2$ without changing the algorithm. The $1/2$ guarantees are oracle-optimal for $k=2$ and asymptotically tight as $k\to\infty$. The value-oracle complexities are $O(Bnk)$ for cardinality, where $B$ is the cardinality bound, $O(n^2k)$ for matroid, and $O(n^3k^2)$ for knapsack.

0.20