A simple near-linear pseudopolynomial time randomized algorithm for subset sum

DOI10.4230/OASICS.SOSA.2019.17MaRDI QIDQ6593573zbMATH OpenFDO

Authors Ce Jin, Hongxun Wu

Publication date 26 August 2024

Full work available at URL https://doi.org/10.4230/OASICS.SOSA.2019.17

zbMATH Keywords

FFTformal power seriessubset sum

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Randomized algorithms (68W20) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• A near-linear pseudopolynomial time algorithm for subset sum
• A faster pseudopolynomial time algorithm for subset sum
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Fast modular subset sum using linear sketching
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations

Cited in

(10)

• Approximating subset sum ratio via partition computations
• \(k\)-SUM in the sparse regime: complexity and applications
• On Wagner's k-tree algorithm over integers
• Scheduling lower bounds via and subset sum
• Minimizing tardy processing time on a single machine in near-linear time
• Minimizing tardy processing time on a single machine in near-linear time
• Almost optimum \(\ell \)-covering of \(\mathbb{Z}_n\)
• Fast n-fold Boolean convolution via additive combinatorics
• Knapsack and subset sum with small items
• Approximation schemes for k-subset sum ratio and k-way number partitioning ratio

This page was built for publication: A simple near-linear pseudopolynomial time randomized algorithm for subset sum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6593573)