Real 3SUM (3SUM)
Jump to navigation
Jump to search
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