# Tag Info

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 $... 0 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. 2 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 ...