论文标题
矩形单调最小产品和应用的改进边界
Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
论文作者
论文摘要
在最近的突破性论文中，Chi等人。 （stoc'22）引入$ \ tilde {o}（n^{\ frac {\ frac {3 +ω} {2}}）$ time算法来计算两个dimensions $ n \ times $ n \ times n $的n $ untery of o（o o（n）$ o（n）$ o（n）$的单调最小量产物。这对先前的$ \ tilde o（n^{\ frac {12 +ω} {5}}）$ time算法有了很大的改善，因此，其应用程序的界限提高了界限。其他几种应用涉及矩形矩阵之间的单调最小产品，即使Chi等人的算法似乎适用于矩形情况，也不简单地进行概括。 在本文中，我们介绍了Chi等人的算法的概括。求解具有多项式有界值的矩形矩阵的单调最小产品。接下来，我们使用此更快的算法来改善矩形单调最小产品的以下应用程序：$ M $包装的单源替换路径，批处理范围模式，$ K $ -K $ -DYCK编辑距离和所有对最短路径的2-APPRXIMATION。我们还使用Chi等人的算法提高了未加权树编辑距离的运行时间。
In a recent breakthrough paper, Chi et al. (STOC'22) introduce an $\tilde{O}(n^{\frac{3 + ω}{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 + ω}{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.
