Solving dense subset-sum problems by using analytical number theory
From MaRDI portal
Publication:1262760
DOI10.1016/0885-064X(89)90025-3zbMath0686.68030MaRDI QIDQ1262760
Mark Chaimovich, Gregory A. Freiman, Zvi Galil
Publication date: 1989
Published in: Journal of Complexity (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Additive number theory; partitions (11P99)
Related Items (6)
On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ Improved broadcast attacks against subset sum problems via lattice oracle ⋮ Fast exact and approximate algorithms for \(k\)-partition and scheduling independent tasks ⋮ Phase transition and finite-size scaling for the integer partitioning problem ⋮ Bisecting binomial coefficients
Cites Work
- An effective formula for the number of solutions of a system of two 0,1- equations
- On sums of subsets of a set of integers
- Finite addition theorems. I
- Erratum to: ``New analytical results in subset-sum problem
- On representation of r-th powers by subset sums
- A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
- Hard Knapsack Problems
- An Algorithm for Large Zero-One Knapsack Problems
- An Effective Formula for the Number of Solutions of Linear Boolean Equations
- Merging and Sorting Applied to the Zero-One Knapsack Problem
- Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Solving dense subset-sum problems by using analytical number theory
