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

DOI10.1016/J.TCS.2015.09.008zbMATH Open1331.68105OpenAlexW1505363495MaRDI QIDQ897863FDOQ897863

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

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

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)

Cites Work

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

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)