0
$\begingroup$

I want to maximise the score of the following table, choosing one item from each column/row, so no two items are on the same row or column. Score to maximise is just adding all the choices together.

$$*\quad A\quad B\quad C\quad D\quad E$$ $$\alpha\quad 16\quad 16\quad 18\quad 18\quad 18$$ $$\beta\quad 20\quad 18\quad 16\quad 12\quad 10$$ $$\gamma\quad 20\quad 18\quad 18\quad 16\quad 16$$ $$\delta\quad 18\quad 18\quad 16\quad 16\quad 8$$ $$\epsilon\quad 10\quad 12\quad 14\quad 14\quad 14$$

Example: ($^{C}$ means chosen)

$$*\quad A\quad B\quad C\quad D\quad E$$ $$\alpha\quad 16^{C}\quad 16\quad 18\quad 18\quad 18$$ $$\beta\quad 20\quad 18\quad 16\quad 12\quad 10^{C}$$ $$\gamma\quad 20\quad 18^{C}\quad 18\quad 16\quad 16$$ $$\delta\quad 18\quad 18\quad 16^{C}\quad 16\quad 8$$ $$\epsilon\quad 10\quad 12\quad 14\quad 14^{C}\quad 14$$

Gives a score of $16+10+18+16+14=74$

Now there are a few ways to do this, but can firstly, someone actually tell me if $88$ really is the best result, and secondly show me how to do it via graph theory. I think I have done it by graph theory matching myself, and will put up my solution as an answer below.

$\endgroup$
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Hungarian_algorithm $\endgroup$ – Erick Wong Oct 30 '14 at 10:03
  • $\begingroup$ @ErickWong Doesn't that minimise? $\endgroup$ – Statisticslove Oct 30 '14 at 10:08
  • $\begingroup$ @Statisticslove If you minimize the matrix with negative numbers, it is the same as maximizing... $\endgroup$ – 5xum Oct 30 '14 at 10:12
  • $\begingroup$ @5xum Have you looked at the method? That couldn't possibly work...? $\endgroup$ – Statisticslove Oct 30 '14 at 10:17
  • 1
    $\begingroup$ Wikipedia suggests that rather than negating the entries, you just subtract them from a sufficiently large value (such as the maximum entry), which is certainly no less effective and maintains a positive entry table. $\endgroup$ – DanielV Oct 30 '14 at 10:23
2
$\begingroup$

Yes, $88$ is the maximum.

First, a score of $88$ can be attained, e.g., by choosing $\alpha E,\beta A,\gamma C,\delta B,\epsilon D$, for a score of $18+20+18+18+14=88$ (I think there are $6$ ways to get a score of $88$ but that's not important.)

To beat $88$, you would need to make at least $90$, since (for some silly reason) all the entries are even numbers. If you were allowed to take the biggest element from each row, you would get $18+20+20+18+14=90$. But you can't do that, because the two $20$s are in the same column. So $88$ is the maximum, like I said.

Alternatively, you could just run through the $5!=120$ possible selections by hand in a few minutes.

$\endgroup$
  • $\begingroup$ Yeah that was the rough logic I had, I wasn't sure how to make it perfectly rigorous, thank you. Why is even silly ;P? $\endgroup$ – Statisticslove Oct 30 '14 at 10:30
  • $\begingroup$ Perhaps "contrived" is a more accurate word than "silly". $\endgroup$ – DanielV Oct 30 '14 at 10:31
  • $\begingroup$ @DanielV How so? $\endgroup$ – Statisticslove Oct 30 '14 at 10:33
  • $\begingroup$ @DanielV I intentionally multiplied all entries by $2$ changed rows and then transposed so I could avoid any punishment for posting an assignment question? I don't think I would bother :P $\endgroup$ – Statisticslove Oct 30 '14 at 10:36
  • 1
    $\begingroup$ @DanielV I think your sum overestimates the probability, because you are adding probabilities of non-disjoint events. $\endgroup$ – bof Oct 30 '14 at 10:45

Your Answer

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

Not the answer you're looking for?Browse other questions tagged or ask your own question.