Real 3SUM: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Real 3SUM (3SUM)}} == Description == Given a set $S$ of reals, determine whether there is a subset of $S$ of size 3 that sums to 0. == Related Problems == Subproblem: 3SUM Related: 3SUM', All-Integers 3SUM == Parameters == <pre>S: the set of reals n: the number of real numbers in the set</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approxim...") |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
S: the set of reals | |||
n: the number of real numbers in the set | |||
n: the number of real numbers in the set | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 12:04, 15 February 2023
Description
Given a set $S$ of reals, determine whether there is a subset of $S$ of size 3 that sums to 0.
Related Problems
Subproblem: 3SUM
Related: 3SUM', All-Integers 3SUM
Parameters
S: the set of reals
n: the number of real numbers in the set
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Gronlund, Pettie | 2014 | $O(n^{2}/((log n)$/(log log n))^{2}/{3}) | Exact | Deterministic | Time | |
| Gronlund, Pettie | 2014 | $O(n^{2}*(log log n)$^{2}/(log n)) | Exact | Randomized | Time | |
| Freund | 2017 | $O(n^{2}*(log log n)$/(log n)) | Exact | Deterministic | Time | |
| Chan | 2018 | $O(n^{2}*(log log n)$^{$O({1})$}/(log n)^{2}) | Exact | Deterministic | Time |
References/Citation
https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/3363541