A Modified Decomposition Algorithm for Maximum Weight Bipartite Matching and Its Experimental Evaluation

Scientific Annals of Computer Science

article

S. Das¹ 

[1] Department of Mathematics, Institute of Science, Banaras Hindu University

关键词: Weighted bipartite matching;    Graph decomposition;    Experimental evaluation;    Random instances of graphs;    Combinatorial optimization.;   

DOI  :  10.7561/SACS.2020.1.39

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

Let G be an undirected bipartite graph with positive integer weights on the edges. We refine the existing decomposition theorem originally proposed by Kao et al., for computing maximum weight bipartite matching. We apply it to design an efficient version of the decomposition algorithm to compute the weight of a maximum weight bipartite matching of G in O( p |V |W0/k(|V |, W0/N))-time by employing an algorithm designed by Feder and Motwani as a subroutine, where |V | and N denote the number of nodes and the maximum edge weight of G, respectively and k(x, y) = log x/ log(x 2/y). The parameter W0 is smaller than the total edge weight W, essentially when the largest edge weight differs by more than one from the second-largest edge weight in the current working graph in any decomposition step of the algorithm. In best the case, W0 = O(|E|) where |E| is the number of edges of G and in the worst case, W0 = W, that is, |E| ≤ W0 ≤ W. In addition, we talk about a scaling property of the algorithm and research a better bound of the parameter W0 . Experimental evaluations of randomly generated data show that the proposed improvement is significant in general.

【 授权许可】

CC BY-ND