Page 1 of 1
6. (5 marks) In the baseball elimination problem, we can show that if w; +ri ≤ wk+rk and team k is eliminated, then team
Posted: Mon Jul 11, 2022 9:55 am
by 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 39 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.