  Min-plus product of two $n\times n$ matrices is a fundamental problem in
algorithm research. It is known to be equivalent to APSP, and in general it has
no truly subcubic algorithms. In this paper, we focus on the min-plus product
on a special class of matrices, called $\delta$-bounded-difference matrices, in
which the difference between any two adjacent entries is bounded by
$\delta=O(1)$. Our algorithm runs in randomized time $O(n^{2.779})$ by the fast
rectangular matrix multiplication algorithm [Le Gall \& Urrutia 18], better
than $\tilde{O}(n^{2+\omega/3})=O(n^{2.791})$ ($\omega<2.373$ [Alman \&
V.V.Williams 20]). This improves previous result of $\tilde{O}(n^{2.824})$
[Bringmann et al. 16]. When $\omega=2$ in the ideal case, our complexity is
$\tilde{O}(n^{2+2/3})$, improving Bringmann et al.'s result of
$\tilde{O}(n^{2.755})$.

Data Structures and Algorithms