Real 3SUM: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
S: the set of reals | $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 == | ||
Latest revision as of 08:28, 10 April 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