A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
From MaRDI portal
Publication:4575810
DOI10.1137/1.9781611974782.69zbMath1423.90210arXiv1610.04712OpenAlexW2949628502MaRDI QIDQ4575810
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://arxiv.org/abs/1610.04712
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (22)
Scheduling lower bounds via AND subset sum ⋮ Approximating multidimensional subset sum and Minkowski decomposition of polygons ⋮ Faster minimization of tardy processing time on a single machine ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Approximating subset sum ratio via subset sum computations ⋮ Change-making problems revisited: a parameterized point of view ⋮ From approximate to exact integer programming ⋮ Algebraic algorithms for variants of subset sum ⋮ Faster algorithms for \(k\)-\textsc{Subset Sum} and variations ⋮ Efficient reductions and algorithms for subset product ⋮ Unnamed Item ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ An improved balanced algorithm for the subset-sum problem ⋮ ON BINARY SOLUTIONS TO SYSTEMS OF EQUATIONS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ More on change-making and related problems ⋮ Faster Pseudopolynomial Time Algorithms for Subset Sum ⋮ On Integer Programming and Convolution. ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Faster algorithms for \(k\)-subset sum and variations
This page was built for publication: A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
