weighted-matching

代码说明：

Given a weighted bipartite graph G =(U,V,E) and a non-negative cost function C = cij associated with each edge (i,j)∈E, the problem of finding a match M ⊂ E such that minimizes ∑ cpq|(p,q) ∈ M, is a very important problem this problem is a classic example of Combinatorial Optimization, where a optimization problem is solved iteratively by solving an underlying combinatorial problem. This problem is also known as the assignment problem. The techniques developed in the Hungarian method assumes that the representation of the underlying bipartite graph is dense and thus emphasizes on the asymptotic complexity of computing the shortest augmenting path which is O((|V|+|U| +|E|)log(|V|+|U|)). However in practice this worst case asymptotic bound was never hit especially in case of the sparse representation of the underlying bipartite graph. In practice we found that the runtime (cputime) of the