Home // Baseball
PPT : An Application of Maximum Flow: The Baseball Elimination Problem
Content Inside :
The Baseball Elimination Problem: Preliminary Analysis
* The maximum number of points Harvard can get is
W = 29 + 4 = 33(by winning all its games)
* Suppose Harvard wins all its remaining games.
It will not be eliminated if and only if
o Brown has no more than u(B) = W-w(B) = 33-27 = 6 wins in the remaining games;
o Cornell has no more than u(C) = W-w(C) = 33-28 = 5 wins in the remaining games;
o Yale has no more than u(Y) = W-w(Y) = 33-33 = 0 wins in the remaining games.
* Let P be the set of all the teams other than Harvard: P = {Y, C, B}
* Let Q be the set of all possible pairs of P-teams:
Q = { (Y,C), (Y,B), (C,B) }
* The total number of games to be played between P-teams is
G = 6+1+1 = 8 .
Solving the Baseball Elimination Problem via Maximum Flow
* The baseball elimination problem can be solved by creating and solving a related instance of maximum flow problem:
o Create a source node O (all the games originate here).
o Create a node for each pair from Q; for each Q-node (i, j), add an arc from O to (i, j); the arc’s capacity is the number of games to be played between i and j.
o Create a node for each team from P; for each Q-node (i, j), add arcs from (i ,j) to P-nodes i and j; cap( (i,j)?i ) = cap( (i,j)?j ) = cap( O ?(i,j) ) .
o Create sink node T (the wins of the teams are recorded here).
o Add an arc from any P-node j to T; the capacity of the arc is u(j) .
My be you need full description for PPT : An Application of Maximum Flow: The Baseball Elimination Problem, you can download this PPT : An Application of Maximum Flow: The Baseball Elimination Problem or online view this PPT : An Application of Maximum Flow: The Baseball Elimination Problem document. This PPT : An Application of Maximum Flow: The Baseball Elimination Problem powerpoint presentation available from category Baseball. Download Seminar Paper Powerpoint Presentation PPT : An Application of Maximum Flow: The Baseball Elimination Problem PPT slide and get information about PPT : An Application of Maximum Flow: The Baseball Elimination Problem.
Category : BaseballSource : www.math.ohiou.edu
File Size : 1.17 Mb
Language : English
Online View : Preview
Download : 67 times
Share this info:
