Published in Volume XXX, Issue 1, 2020, pages 39-67, doi: 10.7561/SACS.2020.1.39

Authors: S. Das

Abstract

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( √ |V|  W’/k(|V|,W’/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(x2/y).
The parameter W’ 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, W’=O(|E|) where |E| is the number of edges of G and in the worst case, W’=W, that is, |E| ≤ W’ ≤ W. In addition, we talk about a scaling property of the algorithm and research a better bound of the parameter W’. Experimental evaluations of randomly generated data show that the proposed improvement is significant in general.

Full Text (PDF)

References

[1] H. Alt, N. Blum, K. Mehlhorn, M. Paul. Computing a Maximum Cardinality Matching in a Bipartite Graph in Time O((n^{1.5} sqrt{ m/log(n\0})). Information Processing Letters 37(4), 237-240, 1991. doi:10.1016/0020-0190(91)90195-N.

[2] J.A. Bondy, U.S.R. Murty. Graph Theory, Graduate Texts in Mathematics. Springer, 2008. doi:10.1007/978-1-84628-970-5.

[3] J. Cheriyan, T. Hagerup, K. Mehlhorn. Can a Maximum Flow be Computed in O(nm) Time? In M.S. Paterson (Ed.) 17th International Colloquium on Automata, Languages and Programming (ICALP 1990), Lecture Notes in Computer Science 443, 235-248. 1990. doi:10.1007/BFb0032035.

[4] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms (3rd Edition). The MIT Press, 2009.

[5] S. Das. A Filtering Technique for All Pairs Approximate Parameterized String Matching. In D. Ghosh, D. Giri, R.N. Mohapatra, E. Savas, K. Sakurai, L.P. Singh (Eds.) 4th International Conference on Mathematics and Computing (ICMC 2018), Communications in Computer and Information Science 834, 97-109, 2018. doi:10.1007/978-981-13-0023-3_10.

[6] S. Das. An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs. Scientific Annals of Computer Science 30(1), 25-37, 2020. doi:10.7561/SACS.2020.1.25.

[7] S. Das, K. Kapoor. Fine-Tuning Decomposition Theorem for Maximum Weight Bipartite Matching. In T.V. Gopal, M. Agrawal, A. Li, S.B. Cooper (Eds.) 11th Annual Conference Theory and Applications of Models of Computation (TAMC 2014), Lecture Notes in Computer Science 8402, 312-322, 2014. doi:10.1007/978-3-319-06089-7_22.

[8] S. Das, K. Kapoor. Weighted Approximate Parameterized String Matching. AKCE International Journal of Graphs and Combinatorics 14(1), 1-12, 2017. doi:10.1016/j.akcej.2016.11.010.

[9] E.A. Dinic, M.A. Kronrod. An Algorithm for the Solution of the Assignment Problem. Soviet Mathematics Doklady 10, 1324-1326, 1969.

[10] R. Duan, S. Pettie. Approximating Maximum Weight Matching in Near-Linear Time. In IEEE 51st Annual Symposium on Foundations of Computer Science, 673-682, 2010. IEEE Computer Society. doi:10.1109/FOCS.2010.70.

[11] T. Feder, R. Motwani. Clique Partitions, Graph Compression and Speeding-Up Algorithms. Journal of Computer and System Sciences 51(2), 261-272, 1995. doi:10.1006/jcss.1995.1065.

[12] M.L. Fredman, R.E. Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Journal of the ACM 34(3), 596-615, 1987. doi:10.1145/28869.28874.

[13] H.N. Gabow. Scaling Algorithms for Network Problems. Journal of Computer and System Sciences 31(2), 148-168, 1985. doi:10.1016/0022-0000(85)90039-X.

[14] H.N. Gabow, R.E. Tarjan. Faster Scaling Algorithms for Network Problems. SIAM Journal on Computing 18(5), 1013-1036, 1989. doi:10.1137/0218069.

[15] G. H. Hardy, J. E. Littlewood, G. Pólya. Inequalities (2nd edition). Cambridge University Press, 1952. doi:10.1017/S0025557200027455.

[16] C. Hazay, M. Lewenstein, D. Sokol. Approximate Parameterized Matching. ACM Transactions on Algorithms 3(3), 2007. doi:10.1145/1273340.1273345.

[17] J.E. Hopcroft, R.M. Karp. An n^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing 2(4), 225-231, 1973. doi:10.1137/0202019.

[18] M. Iri. A New Method for Solving Transportation-Network Problems. Journal of the Operations Research Society of Japan 3(1-2), 27-87, 1960.

[19] M.Y. Kao, T.W. Lam, W.K. Sung, H.F. Ting. A Decomposition Theorem for Maximum Weight Bipartite Matchings with Applications to Evolutionary Trees. In J. Nešetril (Ed.) European Symposium on Algorithms (ESA 1999), Lecture Notes in Computer Science 1643, 438-449. 1999. doi:10.1007/3-540-48481-7_38.

[20] M.Y. Kao, T.W. Lam, W.K. Sung, H.F. Ting. A Decomposition Theorem for Maximum Weight Bipartite Matchings.. SIAM Journal on Computing 31(1), 18-26, 2001. doi:10.1137/S0097539799361208.

[21] B. Korte, J. Vygen. Combinatorial Optimization: Theory and Algorithms (4th edition). Springer-Verlag Berlin Heidelberg, 2008. doi:10.1007/978-3-540-71844-4.

[22] H. W. Kuhn. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly 2(1-2), 83-97, 1955. doi:10.1002/nav.3800020109.

[23] J. Munkres. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics 5(1), 32-38, 1957. doi:10.1137/0105003.

[24] P. Sankowski. Maximum Weight Bipartite Matching in Matrix Multiplication Time. Theoretical Computer Science 410(44), 4480-4488, 2009. doi:10.1016/j.tcs.2009.07.028.

[25] A. Schrijver. Combinatorial Optimization – Polyhedra and Efficiency. Springer, 2003.

[26] D. B. West. Introduction to Graph Theory (2nd edition). Prentice Hall, 2001.

Bibtex

@article{sacscuza:das20amdamwbwee,
  title={A Modied Decomposition Algorithm for Maximum Weight Bipartite Matching and Its Experimental Evaluation,
  author={S. Das},
  journal={Scientific Annals of Computer Science},
  volume={30},
  number={1},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2020},
  pages={39-67},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2020.1.39}
}