SACS | An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs

Published in Volume XXX, Issue 1, 2020, pages 25-37, doi: 10.7561/SACS.2020.1.25

Authors: S. Das

Abstract

The problem of computing a maximum weight matching in a bipartite graph is one of the fundamental algorithmic problems that has played an important role in the development of combinatorial optimization and algorithmics. Let G_w,σ is a collection of all weighted bipartite graphs, each having σ and w as the size of each of the non-empty subset of the vertex partition and the total weight of the graph, respectively. We give a tight lower bound [(w-σ)/σ] + 1 for the set {Wt(mwm(G)) | G ∈G_w,σ } which denotes the collection of weights of maximum weight bipartite matchings of all the graphs in G_w,σ .

Full Text (PDF)

References

[1] J.L. Benjamin, A. Funnell, P.M. Watts, B. Thomsen. A High Speed Hardware Scheduler for 1000-port Optical Packet Switches to Enable Scalable Data Centers. In IEEE 25th Annual Symposium on High-Performance Interconnects (HOTI), 41-48, 2017. doi:10.1109/HOTI.2017.22.

[2] T. Biedl, E.D. Demaine, C.A. Duncan, R. Fleischer, S.G. Kobourov. Tight Bounds on Maximal and Maximum Matchings. Discrete Mathematics 285(1), 7{15, 2004. doi:10.1016/j.disc.2004.05.003.

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

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

[5] S. Das. On Approximate Parameterized String Matching and Related Problems. PhD thesis, Department of Mathematics, Indian Institute of Technology Guwahati, India, 2016. URL: http://gyan.iitg.ernet.in/handle/123456789/734.

[6] 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.

[7] 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.

[8] 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.

[9] P.E. Haxell, A.D. Scott. On Lower Bounds for the Matching Number of Subcubic Graphs. Journal of Graph Theory 85(2), 336-348, 2017.doi:10.1002/jgt.22063.

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

[11] M.A. Henning, A. Yeo. Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph. Graphs and Combinatorics 23, 647-657, 2007. doi:10.1007/s00373-007-0757-5.

[12] M.A. Henning, A. Yeo. Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three. Journal of Graph Theory 72(2), 220-245, 2013. doi:10.1002/jgt.21640.

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

[14] T. Nishizeki, I. Baybars. Lower Bounds on the Cardinality of the Maximum Matchings of Planar Graphs. Discrete Mathematics 28(3), 255-267, 1979. doi:10.1016/0012-365X(79)90133-X.

[15] 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.

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

Bibtex

@article{sacscuza:das20aolbwmwmbg,
  title={An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs},
  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={25–37},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2020.1.25}
}