Improved Bounds for Rectangular Monotone Min-Plus Product
Improved Bounds for Rectangular Monotone Min-Plus Product
复制标题
矩形单调最小加乘积的改进界限
DOI：
--
复制
发表时间：
2022
影响因子：
0.5
通讯作者：
Anita Dürr
中科院分区：
文献类型：
--
作者：
Anita Dürr
在最近的突破性论文中，Chi等人。 （stoc'22）引入$ \ tilde {o}（n^{\ frac {3 + \ omega} {2}} {2}}）$ time算法来计算两个尺寸的两个平方矩阵$ n \ pimes $ n \ times n \ times monotone min-plus product n $和条目由$ o（n）$界定。这在先前的$ \ tilde o（n^{\ frac {12 + \ omega} {5}}}）$ time算法上大大改善，因此，其应用程序的界限提高了界限。其他几种应用涉及矩形矩阵之间的单调最小产品，即使Chi等人的算法似乎适用于矩形情况，也不简单地进行概括。在本文中，我们介绍了Chi等人的算法的概括。求解具有多项式有界值的矩形矩阵的单调最小产品。接下来，我们使用此更快的算法来改善矩形单调最小产品的以下应用程序：$ m $ bunged的单源替换路径，批处理范围模式，$ k $ -dyck编辑距离和所有对的2-透射率最短路径。我们还使用Chi等人的算法提高了未加权树编辑距离的运行时间。
In a recent breakthrough paper, Chi et al. (STOC'22) introduce an $\tilde{O}(n^{\frac{3 + \omega}{2}})$ time algorithm to compute Monotone Min-Plus Product between two square matrices of dimensions $n \times n$ and entries bounded by $O(n)$. This greatly improves upon the previous $\tilde O(n^{\frac{12 + \omega}{5}})$ time algorithm and as a consequence improves bounds for its applications. Several other applications involve Monotone Min-Plus Product between rectangular matrices, and even if Chi et al.'s algorithm seems applicable for the rectangular case, the generalization is not straightforward. In this paper we present a generalization of the algorithm of Chi et al. to solve Monotone Min-Plus Product for rectangular matrices with polynomial bounded values. We next use this faster algorithm to improve running times for the following applications of Rectangular Monotone Min-Plus Product: $M$-bounded Single Source Replacement Path, Batch Range Mode, $k$-Dyck Edit Distance and 2-approximation of All Pairs Shortest Path. We also improve the running time for Unweighted Tree Edit Distance using the algorithm by Chi et al.
更快的单调最小加产品、范围模式和单一来源替换路径
DOI：
--
发表时间：
2021
期刊：
and Programming (ICALP 2021
影响因子：
--
作者：
Gu, Yuzhou;Polak, Adam;Vassilevska Williams, Virginia;Xu, Yinzhan
通讯作者：
Xu, Yinzhan
更快的替换路径和距离敏感性预言机
影响因子：
1.3
作者：
Grandoni, Fabrizio;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska
DOI：
--
发表时间：
2022
期刊：
and Programming (ICALP 2022
影响因子：
--
作者：
Deng, Mingyang;Kirkpatrick, Yael;Rong, Victor;Vassilevska Williams, Virginia;Zhong, Ziqian
通讯作者：
Zhong, Ziqian