Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
share
The goal of this paper is to get truly subcubic algorithms for Min-Plus product for less structured inputs than what was previously known, and to apply them to versions of All-Pairs Shortest Paths (APSP) and other problems. The results are as follows: (1) Our main result is the first truly subcubic algorithm for the Min-Plus product of two n× n matrices A and B with polylog(n) bit integer entries, where B has a partitioning into n^ϵ× n^ϵ blocks (for any ϵ>0) where each block is at most n^δ-far (for δ<3-ω, where 2≤ω<2.373) in ℓ_∞ norm from a constant rank integer matrix. This result presents the most general case to date of Min-Plus product that is solvable in truly subcubic time. (2) The first application of our main result is a truly subcubic algorithm for APSP in a new type of geometric graph. Our result extends the result of Chan'10 in the case of integer edge weights by allowing the weights to differ from a function of the end-point identities by at most n^δ for small δ. (3) In the second application we consider a batch version of the range mode problem in which one is given a length n sequence and n contiguous subsequences, and one is asked to compute the range mode of each subsequence. We give the first O(n^1.5-ϵ) time for ϵ>0 algorithm for this batch range mode problem. (4) Our final application is to the Maximum Subarray problem: given an n× n integer matrix, find the contiguous subarray of maximum entry sum. We show that Maximum Subarray can be solved in truly subcubic, O(n^3-ϵ) (for ϵ>0) time, as long as the entries are no larger than O(n^0.62) in absolute value. We also improve all the known conditional hardness results for the d-dimensional variant of Maximum Subarray.
READ FULL TEXT