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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.