On the Average-Case Complexity of the Min-Sum Product Problem

The min-sum product (also known as min-plus product, distance matrix product, and distance matrix multiplication) is a fundamental operation that has many applications in computer science. It is well known that the min-sum product problem is equivalent to the all-pair shortest paths problem. The time complexity of the best-known algorithm for computing the min-sum product of two matrices in the worst case is only slightly better than cubic time by a poly-logarithmic factor. A truly sub-cubic algorithm for the min-sum product problem in the worst case is a long-standing open problem.In this project, we will focus on the average-case time complexity of the min-sum product problem. Some recent work in the literature showed that min-sum product can be computed significantly faster than cubic time in the average case. However, there is still a gap between the expected running time of those algorithms and the trivial quadratic lower bound. We aim to develop faster algorithms for random inputs that are distributed according to different distributions. Experimental evaluations will be conducted to test the performances of the algorithms in real-world applications.