# MAX-MIN weighted perfect matching (variation)

Suppose that we have a bipartite graph $$G=(V,E)$$ whose edges $$e \in E$$ are assigned to a (descending) sorted list $$e.weight$$ of $$m$$ integer weights. A given matching $$M \subseteq E$$, with respect to index $$i$$, is described by $$l(M,i) \triangleq \mathrm{min}_{e \in M} \{e.weight[i]\}$$, for $$i=1,...,m$$. We also define $$g(M) \triangleq \displaystyle\sum_{i=1}^m l(M,i) = \displaystyle\sum_{i=1}^m\mathrm{min}_{e \in M} \{e.weight[i]\}$$. The objective is to find a perfect matching $$M'$$ which maximizes $$g(M')$$.

The problem must be NP-hard, but I need some help in reducing this to a known well-defined problem. A greedy sub-optimal solution is acceptable as long as there are known bounds.