Maximum Weight Bipartite Matching Algorithm

Context:
- It can range from being an Integer-weight Maximum Weight Bipartite Matching Algorithm to being a Continuous-weight Maximum Weight Bipartite Matching Algorithm.
Example(s):
- Hungarian Algorithm.
See: Maximum Edge Weight.

REferences

(Tantipathananandh et al., 2009) ⇒ Chayant Tantipathananandh, and Tanya Berger-Wolf. (2009). “Constant-factor Approximation Algorithms for Identifying Dynamic Communities.” In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2009). doi:10.1145/1557019.1557110
- QUOTE: … Recently, we have proposed an optimization-based framework for modeling dynamic community structure. Also, we have proposed an algorithm for finding such structure based on maximum weight bipartite matching. …
  … We begin by considering a special case with the assumption that every individual is observed at all times. Under this assumption, we present an algorithm based on maximum weight bipartite matching and show that it is a [math]\displaystyle{ \rho_1 }[/math]-approximation where [math]\displaystyle{ \rho_1 = \alpha/min {\alpha, \beta_2/2} = max {1, 2\alpha/\beta_2} }[/math]. …
  The heart of the above algorithm is finding a maximum weight matching on bipartite graphs, which can be done efficiently, in particular, in polynomial time [24]. Coloring the groups according to the matching can be done in time linear in |V | and |E|. Coloring the individuals can be done in time linear in n and T. Thus, the overall time of the AlgorithmMC is bounded by the time of finding a maximum weight matching on bipartite graphs.

(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).