Maximum Bipartite Matching Task
A Maximum Bipartite Matching Task is a bipartite matching task that requires finding a maximum matching.
- AKA: Maximum Cardinality Bipartite Matching.
- Context:
- Given a bipartite graph [math]\displaystyle{ G = (A \cup B, E) }[/math], find an [math]\displaystyle{ S \subseteq A \times B }[/math] that is a graph matching and is as large as possible.
- See: Bipartite Graph.
References
2014
- http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#In_unweighted_bipartite_graphs
- Matching problems are often concerned with bipartite graphs. Finding a maximum bipartite matching'[1] (often called a maximum cardinality bipartite matching) in a bipartite graph [math]\displaystyle{ G=(V=(X,Y),E) }[/math] is perhaps the simplest problem.
The Augmenting path algorithm finds it by finding an augmenting path from each x ∈ X to [math]\displaystyle{ \ Y }[/math] and adding it to the matching if it exists. As each path can be found in [math]\displaystyle{ \ O(E) }[/math] time, the running time is [math]\displaystyle{ \ O(V E) }[/math]. This solution is equivalent to adding a super source [math]\displaystyle{ s }[/math] with edges to all vertices in [math]\displaystyle{ \ X }[/math], and a super sink [math]\displaystyle{ \ t }[/math] with edges from all vertices in [math]\displaystyle{ \ Y }[/math], and finding a maximal flow from [math]\displaystyle{ \ s }[/math] to [math]\displaystyle{ \ t }[/math]. All edges with flow from [math]\displaystyle{ \ X }[/math] to [math]\displaystyle{ \ Y }[/math] then constitute a maximum matching.
An improvement over this is the Hopcroft–Karp algorithm, which runs in [math]\displaystyle{ O(\sqrt{V}E) }[/math] time. Another approach is based on the fast matrix multiplication algorithm and gives [math]\displaystyle{ O(V^{2.376}) }[/math] complexity,[2] which is better in theory for sufficiently dense graphs, but in practice the algorithm is slower.[3] Finally, for sparse graphs, [math]\displaystyle{ \tilde{O}(E^{10/7}) }[/math] is possible with Madry's algorithm based on electric flows. [4]
- Matching problems are often concerned with bipartite graphs. Finding a maximum bipartite matching'[1] (often called a maximum cardinality bipartite matching) in a bipartite graph [math]\displaystyle{ G=(V=(X,Y),E) }[/math] is perhaps the simplest problem.
- http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#In_weighted_bipartite_graphs
- In a weighted bipartite graph, each edge has an associated value. A maximum weighted bipartite matching is defined as a matching where the sum of the values of the edges in the matching have a maximal value. If the graph is not complete bipartite, missing edges are inserted with value zero. Finding such a matching is known as the assignment problem. The remarkable Hungarian algorithm solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. It uses a modified shortest path search in the augmenting path algorithm. If the Bellman–Ford algorithm is used for this step, the running time of the Hungarian algorithm becomes [math]\displaystyle{ O(V^2 E) }[/math], or the edge cost can be shifted with a potential to achieve [math]\displaystyle{ O(V^2 \log{V} + V E) }[/math] running time with the Dijkstra algorithm and Fibonacci heap.[1]
2003
- (Fischer & Buhmann, 2003) ⇒ Bernd Fischer, and Joachim M. Buhmann. (2003). “Bagging for path-based clustering.” In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(11).
1973
- (Hopcroft & Karp, 1973) ⇒ John E. Hopcroft, and Richard M. Karp. (1973). “An n^5/2 algorithm for maximum matchings in bipartite graphs.” In: SIAM Journal on computing, 2(4).