pipette
ESEspañol

On the Largest Cardinality Subset Sum

Deepak Bhati, Anubhav Dhar, Pranjal Dutta, Mahesh Sreekumar Rajasree, Karol W\k{e}grzycki

Preprint

In the authors' words

We study Largest Cardinality Subset Sum (LCSS): given nonnegative integers and a target , compute a subset summing to with maximum cardinality. We also consider its all-targets version (ATLCSS), which asks for this maximum for every sum . The LCSS problem sits squarely between the subset sum and the knapsack problem. A straightforward dynamic-programming algorithm runs in time and solves ATLCSS, and using Jin and Bringmann (both in STOC 2024, independent work) - knapsack results we achieve a -time deterministic algorithm for LCSS. Our main result is a randomized -time algorithm for LCSS. Then, we complement this result with a randomized -time algorithm for ATLCSS. Together, our two algorithms give a -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 time for every fixed norm with . For , we obtain time, removing the unique-representation assumption required by their algorithm. Both algorithms output an optimal modified vector and a witnessing subset.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: Submitted to STACS 2027