Faster Algorithms for Bounded-Difference Min-Plus Product

Min-plus product of two n × 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, δ-bounded-difference matrices, in which the difference between any two adjacent entries is bounded by δ = O(1). Our algorithm runs in randomized time O(n2.779) by the fast rectangular matrix multiplication algorithm [Le Gall & Urrutia 18], better than Õ(n2+ω/3) = O(n2.791) (ω < 2.373 [Alman & V.V. Williams 20]). This improves the previous result of Õ(n2.824) [Bringmann et al. 16]. When ω = 2 in the ideal case, our complexity is Õ(n2+2/3), improving Bringmann et al.'s result of Õ(n2.755).