Bringman (Subset Sum The Subset-Sum Problem): Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Time Complexity == $\tilde{O}(nt^{1+\epsilon})$ == Space Complexity == \tilde{O}(nt^\epsilon) (https://arxiv.org/abs/1610.04712) == Description == == Approximate? == Approximate Approximation Factor: (n+t)^{-\Omega(1)} error == Randomized? == Yes, Monte Carlo == Model of Computation == == Year == 2017 == Reference == https://arxiv.org/abs/1610.04712") |
No edit summary |
||
| Line 5: | Line 5: | ||
== Space Complexity == | == Space Complexity == | ||
\tilde{O}(nt^\epsilon) | \tilde{O}(nt^\epsilon) words | ||
(https://arxiv.org/abs/1610.04712) | (https://arxiv.org/abs/1610.04712) | ||
| Line 25: | Line 25: | ||
== Model of Computation == | == Model of Computation == | ||
Word RAM | |||
== Year == | == Year == | ||
Latest revision as of 07:54, 10 April 2023
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