Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
复制标题
适用于较少结构化矩阵的真正次三次最小加乘积及其应用
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yinzhan Xu
中科院分区：
文献类型：
--
作者：
V. V. Williams;Yinzhan Xu
本文的目的是获得比以前已知的较少的最低限制产品的Min-Plus产品的亚采购算法，并将其应用于最短路径（APSP）和其他问题的All Pairs版本。结果如下：
（1）我们的主要结果是第一个真正的亚地下算法，用于两种$ n \ times n $矩阵$ a $ a $和$ b $的最低产品，带有$ \ text {polylog}（n）$ bit Integer条目，其中$ b $将分区分为$ n^{\ epsilon} \ times n^{\ epsilon} $ blocks（对于任何$ \ epsilon> 0 $）其中每个块最多是$ n^\ delta $ -far（对于$ \ delta <3- \ omega $，其中$ 2 \ leq \ omega <2.373 $）来自恒定等级整数矩阵的规范。该结果列出了迄今为止最普遍的最低产品的案例，该案例可在真正的亚地带时间内解决。
（2）我们主要结果的第一个应用是一种在新型几何图中的APSP的真正的亚采购算法。在整数边缘权重的情况下，我们的结果扩展了Chan'10的结果，这使权重与端点身份的功能不同，最多最多$ n^\ delta $对于小$ \ delta $。
（3）在第二个应用程序中，我们考虑了范围模式问题的批处理版本，其中为一个范围的$ n $序列和$ n $连续的子序列提供了一个批处理，并要求一个人计算每个子序列的范围模式。我们给出了第一个$ o（n^{1.5- \ epsilon}）$ time $ \ epsilon> 0 $算法对于此批处理范围模式问题。
（4）我们的最终应用程序是最大子阵列问题：给定$ n \ times n $整数矩阵，找到最大输入总和的连续子阵列。我们表明，最大值可以在真正的子立管中解决，只要条目不大于$ o（n^n^，n^{3- \ epsilon}）$（对于$ \ epsilon> 0 $） {0.62}）$绝对值。
我们还改善了最大子阵列的$ d $维二维变体的所有已知条件硬度结果。
The goal of this paper is to get truly subcubic algorithms for Min-Plus product for less structured inputs than what was previously known, and to apply them to versions of All-Pairs Shortest Paths (APSP) and other problems. The results are as follows:
(1) Our main result is the first truly subcubic algorithm for the Min-Plus product of two $n\times n$ matrices $A$ and $B$ with $\text{polylog}(n)$ bit integer entries, where $B$ has a partitioning into $n^{\epsilon}\times n^{\epsilon}$ blocks (for any $\epsilon>0$) where each block is at most $n^\delta$-far (for $\delta<3-\omega$, where $2\leq \omega<2.373$) in $\ell_\infty$ norm from a constant rank integer matrix. This result presents the most general case to date of Min-Plus product that is solvable in truly subcubic time.
(2) The first application of our main result is a truly subcubic algorithm for APSP in a new type of geometric graph. Our result extends the result of Chan'10 in the case of integer edge weights by allowing the weights to differ from a function of the end-point identities by at most $n^\delta$ for small $\delta$.
(3) In the second application we consider a batch version of the range mode problem in which one is given a length $n$ sequence and $n$ contiguous subsequences, and one is asked to compute the range mode of each subsequence. We give the first $O(n^{1.5-\epsilon})$ time for $\epsilon>0$ algorithm for this batch range mode problem.
(4) Our final application is to the Maximum Subarray problem: given an $n\times n$ integer matrix, find the contiguous subarray of maximum entry sum. We show that Maximum Subarray can be solved in truly subcubic, $O(n^{3-\epsilon})$ (for $\epsilon>0$) time, as long as the entries are no larger than $O(n^{0.62})$ in absolute value.
We also improve all the known conditional hardness results for the $d$-dimensional variant of Maximum Subarray.
稀疏图中最短循环和路径的严格硬度
DOI：
10.1137/1.9781611975031.91
发表时间：
2018
期刊：
Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Lincoln, A.;Vassilevska Williams, V.;Williams, R.
通讯作者：
Williams, R.