Computer Science – Data Structures and Algorithms
Scientific paper
2011-12-04
Computer Science
Data Structures and Algorithms
Scientific paper
The {\em maximum cardinality} and {\em maximum weight matching} problems can be solved in time $\tilde{O}(m\sqrt{n})$, a bound that has resisted improvement despite decades of research. (Here $m$ and $n$ are the number of edges and vertices.) In this article we demonstrate that this "$m\sqrt{n}$ barrier" is extremely fragile, in the following sense. For any $\epsilon>0$, we give an algorithm that computes a $(1-\epsilon)$-approximate maximum weight matching in $O(m\epsilon^{-1}\log\epsilon^{-1})$ time, that is, optimal {\em linear time} for any fixed $\epsilon$. Our algorithm is dramatically simpler than the best exact maximum weight matching algorithms on general graphs and should be appealing in all applications that can tolerate a negligible relative error. Our second contribution is a new {\em exact} maximum weight matching algorithm for integer-weighted bipartite graphs that runs in time $O(m\sqrt{n}\log N)$. This improves on the $O(Nm\sqrt{n})$-time and $O(m\sqrt{n}\log(nN))$-time algorithms known since the mid 1980s, for $1\ll \log N \ll \log n$. Here $N$ is the maximum integer edge weight.
Duan Ran
Pettie Seth
Su Hsin-Hao
No associations
LandOfFree
Scaling algorithms for approximate and exact maximum weight matching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Scaling algorithms for approximate and exact maximum weight matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaling algorithms for approximate and exact maximum weight matching will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-393141