|
NBA |
|
RIOT HOME
Basketball: |
IntroductionNote that the following examples come from the RIOT Major League Baseball site, but the same principles that apply to clinching and elimination in baseball also apply to basketball.As the end of the season approaches, baseball fans like to engage in speculation about which teams will advance to the post season and whether their favorite team is still in contention for a playoff berth. Newspapers frequently run headlines in their sports sections declaring that a particular team has been eliminated from contention or that the first place team has clinched a playoff berth. These determinations can often be made by looking at the standings and making a few simple calculations. The RIOT baseball standings can actually tell you when a team has locked up a playoff spot or fallen out of contention days before it is reported anywhere else! The key is taking into account the actual match-ups that remain in the season and enumerating all possible outcomes. Until the final weeks of the season, however, the number of possible outcomes can be astronomically large which makes such an enumeration impractical even on a very fast computer. By using a powerful and pervasive technique of industrial engineering, called Network Optimization, it is possible to accurately perform the necessary calculations without explicitly enumerating all possibilities. Consequently, it is possible for RIOT to determine the playoff prospects of a team a few days, or even weeks, before it is reported by the popular media. The following example, using National League standings as of 9 am, EST, Sunday September 8, shows how this works.
National League East
It is easy to see that the Mets and Phillies are eliminated from first place. Even if they were to win all of their remaining games, they would finish with 82 and 77 wins respectively. Atlanta has already won 86 games, so no matter what happens, they will finish ahead of New York and Philadelphia. Looking at the standings for the National League West, however, it is not apparent that the Giants have been eliminated from first place.
National League West
From looking at the standings, it would appear that San Francisco has a remote chance of catching the first place Dodgers and Padres. This is because even though they are 18 and 1/2 games back, they still have 22 games left to play and the Dodgers and Padres have 21 and 19 games remaining. So, if Los Angeles and San Diego each lose enough games and San Francisco wins enough times, the Giants could conceivably move into first place. A closer look at the schedule, however, reveals that even a miracle winning streak would not allow the Giants to finish in first place. Los Angeles and San Diego will play each other 7 more times before the end of season. There are no ties in baseball, so one of these teams will win at least 4 of those games and finish with a record of 82 and 80 or better. The Giants are eliminated from first place, however, since they can at best achieve a .500 record of 81 and 81. Optimization DetailsCalculating the clinching and elimination numbers for the RIOT baseball standings involves systematically searching for scenarios in which particular teams finish with or without gaining playoff berths. For example, we determined that San Francisco was eliminated from first place in the National League West on September 8th by proving that no feasible scenario exists in which the Giants win the division. The problem of determining whether a team can advance to playoffs given the current league standings and schedule of remaining games can be solved by a single maximum flow calculation (see Hoffman and Rivlin [1] and Schwartz [2]). By introducing additional constraints, we extend this maximum flow formulation to derive integer linear programming problems which find the minimum number of games a given team must win to clinch a playoff spot or avoid elimination from post season play. Robinson [3] takes a similar approach to finding a scenario which maximizes a given team's lead in the final standings. Interested readers should also consult Gusfield and Martel [4], who show how to find the minimum number of games a team must win to avoid elimination from first place by solving a parametric minimum cut problem.For more information on the integer programming formulations and implementation of the RIOT baseball standings, send mail to Professor Hochbaum at dorit@hochbaum.berkeley.edu.
References[1] A. Hoffman and J. Rivlin. "When is a team 'mathematically' eliminated ?" In H.W. Kuhn, editor, Princeton Symposium on Math Programming (1967), Princeton University Press, Princeton, NJ, 1970, pp. 391 - 401.[2] B. Schwartz. "Possible winners in partially completed tournaments." SIAM Review. 8:302-308. 1966 [3] L. W. Robinson "Baseball playoff eliminations: An application of linear programming." Operations Research Letters. 10:67 -74. 1991 [4] D. Gusfield and C. Martel. "A Fast Algorithm for the Generalized Parametric Minimum Cut Problem and Applications." Algorithmica. 7:499 -519. 1992
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
