# Lower bounds on weighted bipartite matching

Suppose a bipartite graph $G=(V_1 \cup V_2,E)$ is given, and a weight $w_e \geq 0$ is associated with each edge $e \in E$. The interest is to match vertices $V_1$ to vertices $V_2$, such that the sum of the edge-weights for the edges included in the matching is maximal. I.e. obtain the maximum weight bipartite matching.

This problem can be solved by e.g. the Hungarian algorithm. However I am not interested in algorithmic approaches, but in theorems stating lower bounds on the value of the maximum weighted matching. I.e. something like: "A matching with weight x is guaranteed to exists if...". A trivial lower bound is 0. However, I am interested in the best bound possible. Ultimately, the best possible theorem would state: "The maximum weighted matching of the bipartite graph G has value x".

I have browsed through various books on the subject, but I have not found suitable results. Lots of results are related to the maximum number of vertices which can be matched (e.g. by extending Hall's Marriage Theorem), though. Maybe it is possible to extend such theorems to incorporate the edge-weights somehow.

FYI, this is somewhat related to a previous question: Good lower bound on matching in bipartite graph

-