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

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,σ} .

Keywords

• bipartite graph
• maximum weight bipartite matching
• lower bound for weights of bipartite matching
• combinatorial optimization
• string matching