6. (5 marks) In the baseball elimination problem, we can show that if w; +ri ≤ wk+rk and team k is eliminated, then team

[answerhappygod]

6 5 Marks In The Baseball Elimination Problem We Can Show That If W Ri Wk Rk And Team K Is Eliminated Then Team 1 (59.36 KiB) Viewed 37 times

6. (5 marks) In the baseball elimination problem, we can show that if w; +ri ≤ wk+rk and team k is eliminated, then team i is also eliminated (where w; denotes the wins of team i, and r; denotes the number of games that team i has left to play). Use this fact to show that in a division containing n teams, we can determine all the eliminated teams by solving O(log n) maxflow problems.