Source-linked AI summary
On the Largest Cardinality Subset Sum
Deepak Bhati, Anubhav Dhar, Pranjal Dutta, Mahesh Sreekumar Rajasree, Karol Węgrzycki
TL;DR
LCSS asks for the largest-cardinality subset summing to a target, adding cardinality information beyond which sums are attainable. The paper gives randomized algorithms for single-target LCSS and for computing maximum cardinalities across all targets. The algorithms run in ˜O(n + √n t) for LCSS and ˜O(n + t^{3/2}) for AT-LCSS, yielding ˜O(n + t min{√n, √t}) for LCSS.
Problem
LCSS asks for the largest-cardinality subset summing to a target, adding cardinality information beyond which sums are attainable.
Source: §1 · pp. 2–3Method
The paper gives randomized algorithms for single-target LCSS and for computing maximum cardinalities across all targets.
Source: §1.2 · pp. 3–4Results
The algorithms run in ˜O(n + √n t) for LCSS and ˜O(n + t^{3/2}) for AT-LCSS, yielding ˜O(n + t min{√n, √t}) for LCSS.
Source: §1.2 · pp. 3–4Takeaways & Limitations
For fixed p ≥ 1, a randomized algorithm outputs an optimal solution to PSSp in ˜O(n + t^{3/2}) time, with failure probability at most 1/3.
Source: §1.2 · p. 4Whether LCSS admits a better algorithm, possibly running in ˜O(n + t), remains open.
Source: §2.1 · p. 7
Abstract
from arXiv · showhide
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.
1 Introduction
LCSS asks for the largest subset summing to a target, retaining cardinality information that ordinary subset-sum algorithms do not preserve. The paper gives randomized algorithms for single-target and all-target LCSS, and applies the all-target result to Projection Subset Sum.
1 Introduction
- LCSS distinguishes attainable representations of the same target by cardinality, placing it between subset sum and knapsack in fine-grained difficulty.The paper’s reduction gives a knapsack instance whose optimum selects a maximum-cardinality subset summing exactly to the target.Source: §1 · p. 2
- Jin’s and Bringmann’s deterministic 0-1 knapsack algorithms give LCSS a ˜O(n + a_max^2)-time algorithm.The paper also contrasts single-target and all-target versions, as in change-making.Source: §1 · p. 2
1.2 Our results
- The randomized LCSS algorithm runs in ˜O(n + √n t) time and computes the exact maximum cardinality with high probability.Its running time reduces the coefficient of t from n to √n, up to polylogarithmic factors.Source: §1.2 · p. 3
- The paper’s LCSS result achieves the same running-time bound as Jin and Mao’s conditional result without relying on its unresolved algorithmic assumption.Jin and Mao’s matching bound depends on an open fast algorithm for decomposing subset sums into an arithmetic progression.Source: §1.2 · p. 4
- AT-LCSS runs in ˜O(n + t^{3/2}) time, and together the single- and all-target bounds yield ˜O(n + t min{√n, √t}) for LCSS.The all-target algorithm’s probability guarantee holds simultaneously for all targets.Source: §1.2 · p. 4
- For each fixed p ≥ 1, the randomized Projection Subset Sum algorithm runs in ˜O(n + t^{3/2}) time and outputs an optimal solution.The ℓ1 algorithm runs in ˜O(n + t) time; both algorithms output a witnessing subset and do not require the unique-representation assumption.Source: §1.2 · p. 4
2 Technical Overview
The overview develops a randomized algorithm for LCSS through a target-cardinality decision problem, then extends heavy–light techniques to compute AT-LCSS for every target. The two approaches use distinct reductions and achieve different running times.
2 Technical Overview
- The bivariate subset-sum routine tracks feasible cardinality–sum pairs under caps, enabling the overview’s algorithms to retain cardinality information.It modifies subset-sum convolution to discard pairs exceeding either cap.Source: §2 · pp. 4–5
2.1 Solving Largest Cardinality Subset Sum
- TCSS asks whether a subset has both a specified sum and cardinality, and the overview uses it to solve LCSS in ˜O(n + √n t) time.The LCSS step binary-searches the largest cardinality using interval checks implemented through TCSS.Source: §2.1 · pp. 5, 7
- The TCSS algorithm separates large and small items, randomly colors indices, and trims pairs whose cardinality deviations are too large.A Chernoff bound ensures a solution is not discarded with high probability; the algorithm runs in ˜O(n + √n t) time.Source: §2.1 · pp. 5–7
2.2 Solving All-targets Largest Cardinality Subset Sum
- For AT-LCSS, heavy-item subset cardinalities and sums are computed with sum at most t and cardinality at most t/τ, while light items use multiplicity reduction; setting τ = Θ(√t) yields total time ˜O(n + t^(3/2)).Source: Handling heavy items · p. 8, Solving All-Targets Largest… · p. 9
- The AT-LCSS approach adapts the heavy–light framework but cannot directly use the faster light-item step for all-target change-making, because AT-LCSS is 0-1.The overview leaves an ˜O(n + t^(4/3))-time AT-LCSS algorithm as an open possibility.Source: Solving All-Targets Largest… · p. 9
3 Preliminaries
The preliminaries establish notation for multisets and sums, define convolution for sets of pairs, and state the probabilistic setting for a Chernoff bound.
3 Preliminaries
- For a multiset Z, Σ(Z) denotes the sum of its elements, while [m] and [m]₀ denote the positive integers through m and the integers from 0 through m.Source: §3 · p. 9
- For sets of pairs, convolution adds the two coordinates pairwise across one element from each set.Source: §3 · p. 9
- The stated Chernoff-bound setup uses independent Bernoulli variables whose sum is Y and whose expectation is μ.Source: §3 · p. 10
4 Largest Cardinality Subset Sum
This section develops a randomized algorithm for LCSS running in Õ(n + √n·t) time, using TCSS as a subroutine and zero-padding with binary search to find the maximum cardinality.
4 Largest Cardinality Subset Sum
- e O(n + √n t) time suffices for randomized TCSS, which the section uses as a subroutine for LCSS.The section presents the TCSS algorithm first, then uses it to solve LCSS.Source: §4 · p. 10
4.1.1 Color coding.
- A random partition assigns the n indices to √n color classes, which are grouped into larger sets at successive levels.Each index independently chooses a uniformly random color; the level-ℓ sets unite consecutive groups of 2^ℓ color classes.Source: §4.1.1 · p. 10
4.1.2 Segregating the input and the solution.
- The analysis segregates items into heavy and light weights and defines layers that partition both the input indices and the fixed solution.The fixed solution has sum t and cardinality k.Source: §4.1.2 · p. 10
4.1.3 Probabilistic guarantees.
- With probability at least 1 − n^-3c, every color class contains O(log n) large solution items and has light-solution weight O((t/√n) log^2 n).The guarantees hold over the random partition and are aggregated in Lemma 16.Source: §4.1.3 · pp. 12–13
4.1.4 Algorithm steps.
- The randomized TCSS algorithm runs in e O(n + √n t) time with error probability at most n^-2c for fixed integer c ≥ 10.Its construction uses probabilistic guarantees from random color coding, with repeated subset-sum computations and pruning of subsets far from expectation.Source: §4.1.4 · p. 13
- The construction’s sumset computations and final array scan take total time Õ(n + sqrt(n)t).The analysis bounds initialization and population of the Boolean array, as well as scanning candidate pairs, by Õ(sqrt(n)t).Source: §4.1.4 · p. 16
4.2 Algorithm for Largest Cardinality Subset Sum
- Appending h − ℓ zero-valued items makes an exact-cardinality-h test equivalent to asking whether a subset has sum t and cardinality in [ℓ, h].The algorithm uses this reduction in binary search to find the maximum feasible cardinality.Source: §4.2 · pp. 16, 18
- Õ(n + sqrt(n)t) time and error probability at most n^-c suffice to solve LCSS for any fixed integer constant c ≥ 10.The algorithm performs a feasibility test and then binary-searches the largest feasible cardinality.Source: §4.2 · p. 18
5 All-Targets Largest Cardinality Subset Sum
AT-LCSS is solved by separating heavy and light items, then combining their contributions with dynamic programming. The randomized algorithm runs in O(n + t^3/2) time, with failure probability at most n^-c.
5.1 Handling heavy items
- Heavy-item maxima for every sum are computed in randomized O(|H| + t^2/τ) time by limiting relevant subsets to fewer than t/τ items.Each heavy item exceeds τ, so a subset of sum at most t has cardinality less than t/τ.Source: §5.1 · p. 19
5.2 Processing light items
- Light items are reduced to O(τ log t) weight–profit pairs while preserving the maximum profit for every sum up to t.Replacing repeated copies of (w, p) with (2w, 2p) preserves the maximum; the reduced multiset is constructed in O(|L| + τ log t) time.Source: §5.2 · pp. 19–20
5.3 Algorithm for All-Targets Largest Cardinality Subset Sum
- The randomized AT-LCSS algorithm runs in O(n + t^3/2) time, with failure probability at most n^-c.Its only randomized step computes heavy-item values correctly for all targets simultaneously with probability at least 1 − n^-c.Source: §5.3 · pp. 21–22
- Dynamic programming combines heavy-item cardinalities with profits from the reduced light-item pairs, then adds back the count of zero-valued items.Preprocessing, the heavy- and light-item procedures, and the dynamic program yield the stated running time; the randomized heavy-item computation succeeds simultaneously for all targets.Source: §5.3 · pp. 21–22
6 Projection Subset Sum
The section applies all-targets largest-cardinality subset sum to Projection Subset Sum, producing optimal modified vectors and witnessing subsets. It gives a randomized near-linear-in-n plus t^(3/2) algorithm for fixed ℓ_p norms, and a faster near-linear-in-n plus t algorithm for ℓ_1.
6.1 Projection Subset Sum for all norms
- The largest-subset recovery routine for target t succeeds with probability at least 5/6 in Õ(n + t^(3/2)) time.It recursively splits the items, uses repeated AT-LCSS runs on each half, and chooses a split maximizing the combined cardinality.Source: §6.1 · pp. 23–24
- For any fixed nonempty subset S, F_p(S) gives the minimum p-th-power modification cost subject to the modified values on S summing to t.An optimal modified vector balances the integer adjustments across S, with adjustment values differing by at most one.Source: §6.1 · p. 24
- For a fixed sum, a largest-cardinality subset minimizes F_p(S), so AT-LCSS supplies the subset choice needed for PSS_p.The algorithm searches attainable sums up to 3t; no subset minimizing F_p has sum greater than 3t.Source: §6.1 · pp. 24–26
- For fixed p ≥ 1, the randomized PSS_p algorithm returns an optimal modified vector and witnessing subset in Õ(n + t^(3/2)) time, with failure probability at most 1/3.It uses AT-LCSS to select a sum and a largest subset of that sum, then constructs the optimal vector.Source: §6.1 · p. 25
6.2 Faster algorithm for Projection Subset Sum on the ℓ1 norm
- The PSS_1 method uses Bringmann’s subset-sum algorithm [4] to find a sum closest to t among nonempty subsets, removing the unique-representation assumption stated for the prior ℓ_1 algorithm [10].For the selected sum, a separate randomized routine recovers a witnessing subset.Source: §6.2 · pp. 27–28
- For PSS_1, the randomized algorithm returns an optimal solution in Õ(n + t) time, with failure probability at most 1/3.It finds a nonempty subset sum closest to t, then recovers a subset with that sum.Source: §6.2 · pp. 27–28
A.1 Fast convolution of sets of pairs
The section computes the sumset of two finite sets of integer pairs using exact integer convolution. Encoding pairs as polynomial exponents avoids coordinate carries and yields Õ(M1M2) time.
A.1 Fast convolution of sets of pairs
- For P, Q ⊆ {−M1,…,M1} × {−M2,…,M2}, their pair-sum set P ⊕ Q can be computed in Õ(M1M2) time.Pairs are encoded as polynomial exponents and exact integer convolution identifies which sums occur.Source: §A.1 · p. 30
- Choosing base 4M1 + 1 prevents carries between the encoded coordinates, so positive product coefficients correspond exactly to pairs in P ⊕ Q.The resulting polynomials and their product have degree O(M1M2).Source: §A.1 · p. 30
A.2 Proof of Lemma 6
The proof extends a generating-function method to track both subset sums and cardinalities. It computes truncated coefficients modulo a random prime, giving a one-sided-error algorithm for the attainable sum-cardinality pairs.
A.2 Proof of Lemma 6
- The randomized algorithm computes {(Σ(S), |S|)} for subsets of size at most k and sum at most t in O((n + kt) polylog(n + kt + 1/δ)) time, with one-sided error at most δ.Every reported pair is attainable; a positive integer coefficient may vanish modulo the chosen prime.Source: §A.2 · p. 30
- A bivariate generating function records subset sums in x and cardinalities in y; the coefficient [x^s y^r] is nonzero exactly when a subset has sum s and cardinality r.The series is truncated to x-degree at most t and y-degree at most k.Source: §A.2 · p. 30
- For prime p > max{k, t}, the truncated generating-function coefficients can be computed modulo p in Õ(n + tk) time.The computation combines coefficient calculation for B(x, y) with a divide-and-conquer computation of the truncated exponential.Source: §A.2 · p. 33
- A random-prime argument bounds the chance that any positive integer coefficient becomes zero modulo p, yielding the stated one-sided error guarantee.The proof applies a union bound over sum-cardinality pairs.Source: §A.2 · p. 33