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

DOI10.1016/J.TCS.2015.09.008MaRDI QIDQ897863zbMATHOpenAlexFDO

Authors Ken C. K. Fong, Minming Li, Hongyu Liang, Linji Yang, Hao Yuan

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.09.008

zbMATH Keywords

matrix multiplicationmin-plus productmin-sum product

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical computation of matrix norms, conditioning, scaling (65F35)

Recommendations

• Average-case complexity of the min-sum matrix product problem
• On the Complexity of Matrix Product
• Average case complexity of linear multivariate problems
• Complexity of multilinear problems in the average case setting
• Tractability of tensor product problems in the average case setting
• Average case complexity of linear multivariate problems. I: Theory
• Average case complexity of linear multivariate problems. II: Applications
• Average case tractability of non-homogeneous tensor product problems
• On the average complexity of multivariate problems
• A survey of average case complexity for linear multivariate problems

Cites work

• scientific article; zbMATH DE number 986995 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• All-pairs shortest paths and the essential subgraph
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
• An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
• Efficient algorithms for the maximum subarray problem by distance matrix multiplication
• Faster all-pairs shortest paths via circuit complexity
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• Gaussian elimination is not optimal
• Matrix multiplication via arithmetic progressions
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• New Bounds on the Complexity of the Shortest Path Problem
• Order Statistics
• Time bounds for selection

Cited in

(1)

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

This page was built for publication: Average-case complexity of the min-sum matrix product problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897863)