CS Paper Radar

On the Largest Cardinality Subset Sum

Deepak Bhati, Anubhav Dhar, Pranjal Dutta, Mahesh Sreekumar Rajasree, Karol Węgrzycki

cs.DS ·submitted 2026-10-21 06:34 UTC · v1

Abstract

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.

Comment
Submitted to STACS 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Faster Deterministic Approximation for Counting Knapsack

cs.DS ·2026-10-10 ·Ce Jin, Jaewoo Park, Barna Saha
top venue similarity 0.71
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

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

cs.DS ·2026-09-27 ·Trevor Vaughn
similarity 0.71
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.

0.12

Multiple-Choice Knapsack with Small Items

cs.DS ·2026-11-11 ·Jakub Pawlewicz
published similarity 0.65
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

Subset Sum in Almost-Linear Time

cs.DS ·2026-10-14 ·Ce Jin, Xiao Mao
theory similarity 0.65
Abstract

We give a deterministic algorithm for finding a subset of the input integers $1\le a_1,\ldots,a_n \le Δ$ that sums to the target $t$ in $\mathcal{O}(n+Δ^{1+o(1)})$ time. This improves upon the previous $\widetilde{\mathcal{O}}(n + Δ^{1.5})$-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and achieves almost tight dependence on $Δ$ assuming SETH. We use an inverse theorem for subset sums due to Conlon, Fox, and Pham (2023), and develop a quotient variant of economic cap covering from the polytope approximation literature.

0.49

A PTAS for Non-Adaptive Stochastic Top-$k$ Sum under General Combinatorial Constraints

cs.DS cs.CC ·2026-09-03 ·Yu Liu
similarity 0.64
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

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

cs.DS ·2026-10-09 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.64
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

Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis

cs.DS ·2026-10-22 ·Deepak Bhati, Pranjal Dutta, Antoine Joux, Mahesh Sreekumar Rajasree, Karol Wegrzycki
top venuetheory similarity 0.63
Abstract · 66 pages, 2 figures, published in FOCS 2026

The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime $M = 2^{o(n)}$, where the pigeonhole principle guarantees that a solution exists, and the main challenge is to find one efficiently. A straightforward dynamic-programming algorithm runs in time poly(n).$M$. After a sequence of improvements, the current best algorithm, due to Jin, Williams, and Zhang (ESA 2025), achieves running time poly(n).$M^{1/3}$. In this work, we give the first poly(n).$M^{o(1)}$-time algorithm for Equal Subset Sum in the regime $M = 2^{o(n)}$. We complement this algorithmic result with a tight conditional lower bound showing that any substantial improvement would require a major breakthrough in approximation algorithms for lattice problems, building on recent techniques of Vafa and Vaikuntanathan (STOC 2025). Finally, we show that our techniques yield an asymptotically faster algorithm for the regime when $M = Θ(2^{n})$: a poly(n)$\cdot 2^{n/4}$-time algorithm in the average case.

0.32

A Note on Truly Subquadratic Time FPTAS for Knapsack

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