Faster min-plus product for monotone instances

In this paper, we show that the time complexity of monotone min-plus product of two n× n matrices is Õ(n(3+ω)/2)=Õ(n2.687), where ω < 2.373 is the fast matrix multiplication exponent [Alman and Vassilevska Williams 2021]. That is, when A is an arbitrary integer matrix and B is either row-monotone or column-monotone with integer elements bounded by O(n), computing the min-plus product C where Ci,j=minkAi,k+Bk,j takes Õ(n(3+ω)/2) time, which greatly improves the previous time bound of Õ(n(12+ω)/5)=Õ(n2.875) [Gu, Polak, Vassilevska Williams and Xu 2021]. Then by simple reductions, this means the case that A is arbitrary and the columns or rows of B are bounded-difference can also be solved in Õ(n(3+ω)/2) time, whose previous result gives time complexity of Õ(n2.922) [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. So the case that both of A and B are bounded-difference also has Õ(n(3+ω)/2) time algorithm, whose previous results give time complexities of Õ(n2.824) [Bringmann, Grandoni, Saha and Vassilevska Williams 2016] and Õ(n2.779) [Chi, Duan and Xie 2022]. Many problems are reducible to these problems, such as language edit distance, RNA-folding, scored parsing problem on BD grammars [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. Thus, their complexities are all improved.