Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths

Given a directed graph with a capacity on each edge, the all-pairs bottleneck paths (APBP) problem is to determine, for all vertices s and t, the maximum flow that can be routed from s to t. For dense graphs this problem is equivalent to that of computing the (max, min)-transitive closure of a real-valued matrix. In this paper, we give a (max, min)-matrix multiplication algorithm running in time O(n(3+ω)/2) ≤ O(n2.688), where ω is the exponent of binary matrix multiplication. Our algorithm improves on a recent O(n2+ω/3) ≤ O(n2.792)- time algorithm of Vassilevska, Williams, and Yuster. Although our algorithm is slower than the best APBP algorithm on vertex capacitated graphs, running in O(n2.575) time, it is just as efficient as the best algorithm for computing the dominance product, a problem closely related to (max, min)-matrix multiplication. Our techniques can be extended to give subcubic algorithms for related bottleneck problems. The all-pairs bottleneck shortest paths problem (APBSP) asks for the maximum flow that can be routed along a shortest path. We give an APBSP algorithm for edge-capacitated graphs running in O(n(3+ω)/2) time and a slightly faster O(n2.657)-time algorithm for vertex-capactitated graphs. The second algorithm significantly improves on an O(n2.859)-time APBSP algorithm of Shapira, Yuster, and Zwick. Our APBSP algorithms make use of new hybrid products we call the distance-max-min product and dominance-distance product.

给定一个每条边都有容量的有向图，全对瓶颈路径（APBP）问题是要确定对于所有顶点\(s\)和\(t\)，从\(s\)到\(t\)可传输的最大流。对于稠密图，这个问题等同于计算一个实值矩阵的（最大，最小）-传递闭包问题。在本文中，我们给出了一个（最大，最小）-矩阵乘法算法，其运行时间为\(O(n^{(3+\omega)/2})\leq O(n^{2.688})\)，其中\(\omega\)是二进制矩阵乘法的指数。我们的算法改进了Vassilevska、Williams和Yuster最近提出的一个运行时间为\(O(n^{2+\omega/3})\leq O(n^{2.792})\)的算法。尽管我们的算法比顶点有容量图上的最佳APBP算法慢，后者运行时间为\(O(n^{2.575})\)，但它与计算优势积（一个与（最大，最小）-矩阵乘法密切相关的问题）的最佳算法一样高效。 我们的技术可以扩展，为相关的瓶颈问题给出次立方算法。全对瓶颈最短路径问题（APBSP）是求可沿最短路径传输的最大流。我们给出了一个用于边有容量图的APBSP算法，其运行时间为\(O(n^{(3+\omega)/2})\)，以及一个用于顶点有容量图的稍快的运行时间为\(O(n^{2.657})\)的算法。第二个算法显著改进了Shapira、Yuster和Zwick提出的一个运行时间为\(O(n^{2.859})\)的APBSP算法。我们的APBSP算法利用了我们称为距离 - 最大 - 最小积和优势 - 距离积的新型混合积。