A new property and a faster algorithm for baseball elimination
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Applications of mathematical programming (90C90)
The teams in a tornament are competing for first place. At each point in the season we have for each team \((i)\) a record of the number of wins \((w_i)\) so far and the number of games left to play against each team \(j\), labeled, \(g_{ij}\). With this information in hand, can one determine which teams cannot possibly win first place? Such a team is said to have been eliminated. It was shown in 1966 that a single maximum flow computation was needed to decide if a given team was eliminated. This paper describes an algorithm that will determine all eliminated teams. More importantly it does so in time proportional to a single maximum flow computation.
- The structure and complexity of sports elimination numbers
- This house proves that debating is harder than soccer
- The computational complexity of the elimination problem in generalized sports competitions
- A connection between sports and matroids: how many teams can we beat?
- An application of integer programming to playoff elimination in football championships
- A connection between sports and matroids: how many teams can we beat?
- The computational complexity of the elimination problem in generalized sports competitions
- Soccer is Harder Than Football
- The structure and complexity of sports elimination numbers
- Refining the complexity of the sports elimination problem
This page was built for publication: A new property and a faster algorithm for baseball elimination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2719163)
