Bringman (Subset Sum The Subset-Sum Problem)
Jump to navigation
Jump to search
Time Complexity
$\tilde{O}(nt^{1+\epsilon})$
Space Complexity
\tilde{O}(nt^\epsilon) words
(https://arxiv.org/abs/1610.04712)
Description
Approximate?
Approximate
Approximation Factor: (n+t)^{-\Omega(1)} error
Randomized?
Yes, Monte Carlo
Model of Computation
Word RAM
Year
2017