A faster pseudopolynomial time algorithm for subset sum

DOI10.1137/1.9781611974782.68MaRDI QIDQ4575809zbMATH OpenOpenAlexFDO

Authors Konstantinos Koiliaris, Chao Xu

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.68

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• Faster Pseudopolynomial Time Algorithms for Subset Sum
• A near-linear pseudopolynomial time algorithm for subset sum
• Faster algorithms for \(k\)-subset sum and variations
• Fast modular subset sum using linear sketching
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem

Cited in

(24)

• Change-making problems revisited: a parameterized point of view
• An improved balanced algorithm for the subset-sum problem
• More on change-making and related problems
• Actively secure setup for SPDZ
• Faster algorithms for \(k\)-subset sum and variations
• Faster minimization of tardy processing time on a single machine
• Approximating multidimensional subset sum and Minkowski decomposition of polygons
• Irredundant Set Faster Than O(2 n )
• A near-linear pseudopolynomial time algorithm for subset sum
• Computing area in presentations of the trivial group
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• The Hurwitz action in complex reflection groups
• Equal-subset-sum faster than the meet-in-the-middle
• Capacitated dynamic programming: faster knapsack and graph algorithms
• On binary solutions to systems of equations
• Fast modular subset sum using linear sketching
• scientific article; zbMATH DE number 7651168 (Why is no real title available?)
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations
• A simple near-linear pseudopolynomial time randomized algorithm for subset sum
• Faster minimization of tardy processing time on a single machine
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
• Fast n-fold Boolean convolution via additive combinatorics

This page was built for publication: A faster pseudopolynomial time algorithm for subset sum

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