Maximum weight bipartite matching in matrix multiplication time

In this paper we consider the problem of finding maximum weight matchings in bipartite graphs with nonnegative integer weights. The presented algorithm for this problem works in 1 time, where ω is the matrix multiplication exponent, and W is the highest edge weight in the graph. As a consequence of this result we obtain time algorithms for computing: minimum weight bipartite vertex cover, single source shortest paths and minimum weight vertex disjoint s-t paths. All of the presented algorithms are randomized and with small probability can return suboptimal solutions.