New answers tagged


Actually, I realized what I was missing shortly after posting the question and squinting at the pictures again. Instead of deleting, figured I'd simply post the answer for future reference. The thing I was missing was that the new matching won't have the same edges as the original matching. In the first figure, 3->5->2->4 is such a path and 2->4 $...


If you want to maximize the sum of the scores for each participant, this is an instance of the assignment problem; use the Hungarian algorithm, or any other algorithm for computing a maximum matching. You might also be interested in stable marriage algorithms, which have a different notion of fairness.


Observing that there exists an optimal solution such that for any $i_1<i_2$ , $f(i_1)\le f(i_2)$ (otherwise, we can swap $f(i_1)$ and $f(i_2)$), there is a dynamic programming algorithm solving your problem. We sort $A$ and $B$ firstly. Suppose $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_m\}$, where $a_1<\cdots<a_n$ and $b_1<\cdots <b_m$. Let ...

Top 50 recent answers are included