I suppose you are all familiar with the baseball elimination problem (it is about determining whether some team with particular number of points can finish in the first place, when there are still such and such games to be played by other teams).

The rules there are rather simple - the winner gets a point, while the loser gets nothing. But what if we changed those rules, so that the loser would get -1 point for each game lost. Could it still be brought down to the max-flow problem then? I've been thinking about this, but there's no way to do that in my opinion.


I am not familiar with the baseball elimination problem, but nevertheless, if you can solve the original problem, then you can solve the new problem. Here is why. For each game that a team has to play, deduct 1 from its score. Instead of awarding it 1 point if it wins, award it 2 points. It still gets 0 if it loses. This moves us closer to the original problem.

In order to get the original problem as stated, we divide all scores by 2, converting the 2 point award to a 1 point award. This reduces the new problem to the original one, which you already know how to solve.

  • $\begingroup$ This almost works but not quite, because in a max-flow formulation the 2 points that are awarded could be split between the teams. It seems that you could just divide the scores by 2 though and do some rounding to make it work. $\endgroup$ – Tom van der Zanden Oct 4 '15 at 13:51
  • $\begingroup$ Yes, this is one more step in the reduction. I'll update the answer. $\endgroup$ – Yuval Filmus Oct 4 '15 at 13:52
  • $\begingroup$ Fantastic! I haven't thought about this. $\endgroup$ – Jules Oct 4 '15 at 14:15

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.