pipette
ENEnglish

On the Largest Cardinality Subset Sum

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

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Submitted to STACS 2027