Given a weighted bipartite graph with n vertices and m edges, the \mathit{maximum~weight~bipartite~matching problem is to find a set of vertex-disjoint edges with the maximum weight. This classic problem has been extensively studied for over a century. In this paper, we present a new streaming algorithm for the maximum weight bipartite matching problem that uses O(n) space and O(m) passes, which breaks the n-pass barrier. All the previous  algorithms either require \Omega(n \log n) passes or only find an approximate solution. To achieve this pass bound, our algorithm combines a number of techniques  from different fields such as the interior point method (IPM), symmetric diagonally dominant (SDD ) system solving , the isolation lemma, and LP duality. To the best of our knowledge, this is the first work that implements the SDD solver and IPM in the streaming model in \widetilde{O}(n) spaces for graph matrix. All the previous IPMs only focus on optimizing the running time, regardless of the space usage . The LP solver for general matrix is impossible to be implemented in%DIFDELCMD < \widetilde{O}%%% (n) spaces .
Given a weighted bipartite graph with n vertices and m edges, the maximum weight bipartite matching problem is to find a set of vertex-disjoint edges with the maximum weight. This classic problem has been extensively studied for over a century. In this paper, we present a new streaming algorithm for the maximum weight bipartite matching problem that uses O(n) space and O(m) passes, which breaks the n-pass barrier. All the previous streaming algorithms either require \Omega(n \log n) passes or only find an approximate solution. Our streaming algorithm constructs a subgraph with n edges of the input graph in (\sqrt{m from different fields , most notably the construction ofspace-efficient interior point method (IPM), SDD system solvers , the isolation lemma, and LP duality. To the best of our knowledge, this is the first work that implements the SDD solvers and IPMs in the streaming model in \widetilde{O}(n) spaces for graph matrices; previous IPM algorithms only focus on optimizing the running time, regardless of the space usage %DIFDELCMD < \widetilde{O}%%% .
R
\mathit{maximum~weight~bipartite~matching
maximum weight bipartite matching
A
streaming
R
To achieve this pass bound, our algorithm combines a number of techniques
Our streaming algorithm constructs a subgraph with n edges of the input graph in
A
(\sqrt{m
R
such as the
, most notably the construction of
A
space-efficient
R
symmetric diagonally dominant (SDD ) system solving
SDD system solvers
R
solver and IPM
solvers and IPMs
R
matrix. All the previous IPMs
matrices; previous IPM algorithms
D
. The LP solver for general matrix is impossible to be implemented in
D
(n) spaces