Average-case complexity of the min-sum matrix product problem
type: Item
instance of: scholarly article
title: Average-case complexity of the min-sum matrix product problem
zbMATH Open document ID: 1331.68105
author: Ken C. K. Fong
author: Minming Li
author: Hongyu Liang
author: Linji Yang
author: Hao Yuan
published in: Theoretical Computer Science
publication date: 2015-12-08T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65F35
zbMATH DE Number: 6517429
zbMATH Keywords: min-sum product
zbMATH Keywords: min-plus product
zbMATH Keywords: matrix multiplication
MaRDI profile type: Publication
full work available at URL: j.tcs.2015.09.008
OpenAlex ID: W1505363495
cites work: Q4091421
cites work: More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
cites work: Faster all-pairs shortest paths via circuit complexity
cites work: An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
cites work: Gaussian elimination is not optimal
cites work: Matrix multiplication via arithmetic progressions
cites work: An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
cites work: Efficient algorithms for the maximum subarray problem by distance matrix multiplication
cites work: A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
cites work: New Bounds on the Complexity of the Shortest Path Problem
cites work: Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
cites work: All-pairs shortest paths and the essential subgraph
cites work: Q3122914
cites work: An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
cites work: A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
cites work: Time bounds for selection
cites work: Order Statistics
DOI: 10.1016/J.TCS.2015.09.008
Recommended article: Average-Case Complexity of the Min-Sum Matrix Product Problem
Recommended article: On the Complexity of Matrix Product
Recommended article: Average case complexity of linear multivariate problems
Recommended article: Complexity of multilinear problems in the average case setting
Recommended article: Tractability of tensor product problems in the average case setting
Recommended article: Average case complexity of linear multivariate problems. I: Theory
Recommended article: Average case complexity of linear multivariate problems. II: Applications
Recommended article: Average case tractability of non-homogeneous tensor product problems
Recommended article: On the average complexity of multivariate problems
Recommended article: A survey of average case complexity for linear multivariate problems
description: scientific article; zbMATH DE number 6517429