Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

DOI10.1145/3357713.3384308OpenAlexW3035306598MaRDI QIDQ5144983

Vasileios Nakos, Karl Bringmann

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2107.13206

zbMATH Keywords

convolutionrestricted sumsetsubset sumoutput-sensitivepseudopolynomial

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Approximating subset sum ratio via subset sum computations ⋮ Faster algorithms for \(k\)-\textsc{Subset Sum} and variations ⋮ Faster algorithms for \(k\)-subset sum and variations

This page was built for publication: Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum