Maximum Weight Bipartite Matching Task

Context:
- It can be solved by a Maximum Weight Bipartite Matching Machine (that applies a Maximum Weight Bipartite Matching Algorithm.
Example(s):
- Hungarian Assignment Algorithm.
See: Graph Link Prediction Task, Weighted Graph, Matching Task.

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.

(Belongie et al., 2002) ⇒ Serge Belongie, Jitendra Malik, and Jan Puzicha. (2002). “Shape matching and object recognition using shape contexts.” In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(4).
- QUOTE: … H ∑ i C pi;q i 2 subject to the constraint that the matching be one-to-one, ie, is a permutation. This is an instance of the square assignment (or weighted bipartite matching) problem, which can be solved inO N3 time using the Hungarian method [42]. ...