In the baseball elimination problem, there is a league consisting of n teams. At some point during the season, team i has wi wins and gij games left to play against team j. A team is eliminated if it cannot possibly finish the season in first place or tied for first place. The goal is to determine exactly which teams are eliminated. The problem is not as easy as many sports writers would have you believe, in part because the answer depends not only on the number of games won and left to play but also on the schedule of remaining games. In the 1960's, Schwartz showed how to determine whether one particular team is eliminated using a maximum flow computation. This paper indicates that the problem is not as difficult as many mathematicians would have you believe. For each team i, let gi denote the number of games remaining. We prove that there exists a value W such that team i is eliminated if and only if wi + gi < W. Using this surprising fact, we can determine all eliminated teams in time proportional to a single maximum flow computation in a graph with n nodes; this improves upon the previous best known complexity bound by a factor of n.
(Based on a paper by Kevin D. Wayne in SODA 1999 and SIAM J. Discrete Math. 2001)