Average-case complexity of the min-sum matrix product problem

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)76-86
Journal / PublicationTheoretical Computer Science
Volume609
Issue numberPt. 1
Online published10 Sept 2015
Publication statusPublished - 4 Jan 2016

Abstract

We study the average-case complexity of mm-sum product of matrices, which is a fundamental operation that has many applications in computer science. We focus on optimizing the number of "algebraic" operations (i.e., operations involving real numbers) used in the computation, since such operations are usually expensive in various environments. We present an algorithm that can compute the min-sum product of two n x n real matrices using only (n2) algebraic operations, given that the matrix elements are drawn independently and identically from some fixed probability distribution satisfying several constraints. This improves the previously best known upper-bound of (n2 log n). The class of probability distributions under which our algorithm works include many important and commonly used distributions, such as uniform distributions, exponential distributions, folded normal distributions, etc.
In order to evaluate the performance of the proposed algorithm, we performed experiments to compare the running time of the proposed algorithm with algorithms in [1]. The experimental results demonstrate that our algorithm achieves significant performance improvement over the previous algorithms. 

Research Area(s)

  • Min-sum product, Min-plus product, Matrix multiplication, SHORTEST-PATH ALGORITHM

Citation Format(s)

Average-case complexity of the min-sum matrix product problem. / Fong, Ken C.K. ; Li, Minming; Liang, Hongyu et al.
In: Theoretical Computer Science, Vol. 609, No. Pt. 1, 04.01.2016, p. 76-86.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review