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

Ken FONG*, Minming LI, Hongyu LIANG, Linji YANG, Hao YUAN

*Corresponding author for this work

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review


We study the average-case complexity of min-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 × n real matrices using only O(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 O(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, and folded normal distributions. 

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[7]. The experimental results demonstrate that our algorithm achieves significant performance improvement over the previous algorithms.

Original languageEnglish
Title of host publicationAlgorithms and Computation: 25th International Symposium, ISAAC 2014, Proceedings
EditorsHee-Kap AHN, Chan-Su SHIN
Place of PublicationSwitzerland
PublisherSpringer, Cham
Number of pages12
ISBN (Electronic)9783319130750
ISBN (Print)9783319130743
Publication statusPublished - 8 Nov 2014
Externally publishedYes
EventAlgorithms and computation : 25th International Symposium, ISAAC 2014 - Jeonju, Korea, Republic of
Duration: 15 Dec 201417 Dec 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


SymposiumAlgorithms and computation : 25th International Symposium, ISAAC 2014
Country/TerritoryKorea, Republic of

Bibliographical note

This work was fully supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 122512].


Dive into the research topics of 'Average-case complexity of the min-sum matrix product problem'. Together they form a unique fingerprint.

Cite this