Threesomes, Degenerates, and Love Triangles
Threesomes, Degenerates, and Love Triangles
复制标题
DOI：
10.1145/3185378
复制
发表时间：
2018-08-01
影响因子：
2.5
通讯作者：
Pettie, Seth
中科院分区：
文献类型：
--
作者：
Gronlund, Allan;Pettie, Seth
3SUM问题是确定一组N实数，无论是否有3个总和为零。人们普遍认为，微不足道的O（n（2）） - 时间算法在真实RAM上是最佳的，即使在非均匀的线性决策树模型中，也是最佳的。多年来，这种猜想的后果已经揭示。这个3sum的猜想暗示了欧米茄（N（2））在计算几何学上许多问题上的下限，并且整数输入的猜想的变体意味着三角枚举，动态图形算法和匹配数据结构的字符串。 ，我们驳斥了3sum在实际RAM中需要Omega（n（2））的猜想，并更加强行反驳其复杂性是线性决策树模型中其复杂性是Omega（n（2））。特别是，我们证明了3SUM的决策树复杂性为O（n（3/2）根log n），并给出两个子限制3SUM算法，这是一种在O（n（n（2）/（log n/log log）中，一个确定性的算法n）（2/3））时间和一个随机的时间（n（2）/（log n/log log n）时间高的时间。所有奇数k> = = 3的变化线性退化测试。从本文中，我们给出了一个亚基算法，用于通过实价矩阵的（min， +） - 乘积的概括，并将其应用于查找零重量的三角形问题的问题 - 加权图。 ）/ log n）。
The 3SUM problem is to decide, given a set of n real numbers, whether any three sum to zero. It is widely conjectured that a trivial O(n(2))-time algorithm is optimal on the Real RAM, and optimal even in the nonuniform linear decision tree model. Over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies Omega(n(2)) lower bounds on numerous problems in computational geometry, and a variant of the conjecture for integer inputs implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures.In this article, we refute the conjecture that 3SUM requires Omega (n(2)) in the Real RAM and refute more forcefully the conjecture that its complexity is Omega (n(2)) in the linear decision tree model. In particular, we prove that the decision tree complexity of 3SUM is O(n(3/2)root log n) and give two subquadratic 3SUM algorithms, a deterministic one running in O(n(2)/(log n/ log log n)(2/3)) time and a randomized one running in O(n(2)/(log n/ log log n) time with high probability. Our results lead directly to improved bounds on the decision tree complexity of k-variate linear degeneracy testing for all odd k >= 3.Finally, we give a subcubic algorithm for a generalization of the (min, +)-product over real-valued matrices and apply it to the problem of finding zero-weight triangles in edge-weighted graphs. We give a depth-O(n(5/2)root log n) decision tree for this problem, as well as a deterministic algorithm running in time O(n(3)/(log log n)(2)/ log n).