TY - GEN
T1 - Average-Case Complexity of the Min-Sum Matrix Product Problem
AU - Fong, Ken
AU - Li, Minming
AU - Liang, Hongyu
AU - Yang, Linji
AU - Yuan, Hao
PY - 2014/12
Y1 - 2014/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84921734045&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84921734045&origin=recordpage
U2 - 10.1007/978-3-319-13075-0_4
DO - 10.1007/978-3-319-13075-0_4
M3 - 32_Refereed conference paper (with ISBN/ISSN)
SN - 9783319130743
T3 - Lecture Notes in Computer Science
SP - 41
EP - 52
BT - Algorithms and Computation
A2 - Ahn, Hee-Kap
A2 - Shin, Chan-Su
PB - Springer
T2 - 25th International Symposium on Algorithms and Computation (ISAAC 2014)
Y2 - 15 December 2014 through 17 December 2014
ER -