# 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.

Thank you in advance.

• @MishaLavrov Thanks for your reply. I restated to clarify ambiguities. – JackDaniels897 Sep 10 at 15:52
• It makes sense now. Maybe a linear program would work here as it does for max-weight matching? I'm not quite sure. – Misha Lavrov Sep 10 at 20:06