University:
Massachusetts Institute of Technology
Course:
6.046J | Design and Analysis of Algorithms
Academic year:

2023
Views:

364

Pages:

2
Author:

Denzel Ibarra

Lecture 14 Baseball Elimination 6.046J Spring 2015 Lecture 14: Baseball Elimination In this lecture, we will be studying how to use max-ﬂow algorithms to compute elimination of sports teams in a league. Concretely, let us consider the standings of the AL Eastern Division of the Major League Baseball on August 30, 19961 , without Detroit’s record. Team NY Baltimore Boston Toronto Detroit Table 1: Standings of AL East on August 30, 1996. Wins (wi ) Losses (fi ) To Play (ri ) Games against each other 7 4 3 5 – 28 59 75 2 4 4 – 5 28 63 71 – 4 0 2 7 28 65 69 4 – 0 4 4 28 71 63 0 0 – 4 3 28 ? ? NY Ba Bo T D From this chart, how can we ﬁgure out if a team is eliminated? A naive sports writer can only compute that Team i is eliminated if wi + ri < wj for some other j. For example, if Detroit’s record was w5 = 46, then Detroit is certainly eliminated since w5 + r5 = 46 + 28 < 75 = w1 . This condition, however, is suﬃcient, but not necessary. For instance, consider w5 = 47. Though w5 + r5 = 75, either NY or Baltimore will reach 76 wins since they have 5 games left against each other. How can we determine if Detroit is eliminated for arbitrary values of w5 ? To answer this question, we can use max-ﬂow. Consider the Figure 1, where capacity between s and node i − j is the number of games left to be played between team i and j, between node i − j and node k = 1, 2, 3, 4 is inﬁnity, and node k and t is w5 + r5 − wk . The intuition for the construction of the graph is that we will assume Detroit win all r5 games, and try to keep the number of wins per team to be less than or equal to the total possible wins of Detroit (≤ w5 + r5 ). Theorem 1. Team 5 (Detroit) is eliminated if and only if max-ﬂow does not saturate all edges leaving the source, i.e., max ﬂow value < 26. Proof. Saturation of the edge capacity corresponds to playing all the remaining games. If all the games cannot be played, while keeping the total number of wins of a team to be less than or equal to w5 + r5 , then Team 5 is eliminated. 1 roughly speaking! 1 Lecture 14 Baseball Elimination 6.046J Spring 2015 Figure 1: Flow network to determine if Team 5 is eliminated In Figure 1, the min-cut (S, T ) is S = {s, 1 − 2, 1 − 3, 2 − 3, 1, 2, 3} and T = {1 − 4, 2 − 4, 3 − 4, 4, t}. The capacity of the min-cut c(S, T ) = 4 + 4 + 4 + 1 + 5 + 7 = 25 < 26. Therefore, Team 5 Detroit is eliminated. Alternate explanation: Note that the max-ﬂow will ﬁnd the subset of teams that eliminates Team 5. In this example, consider subset of teams 1,2, and 3. The total number of wins among the 3 teams is 215 wins, and they have 14 games left to play with each other. Then there will be 229 total wins at the end of the regular season. This implies that there exists at least one team that wins 1 229 l = 77 games. 3 Therefore, if Detroit only has 48 wins, then it is certainly eliminated (48 + 28 = 76 < 77). We can ﬁnd such set using max-ﬂow and max-ﬂow min-cut theorem. 2