New property and a faster algorithm for baseball elimination

Research output: Contribution to conferencePaperpeer-review

3 Scopus citations

Abstract

In the baseball elimination problem, there is a league consisting of n teams. At some point during the season, team i has wi wins and gij games left to play against team j. A team is eliminated if it cannot possibly finish the season in first place or tied for first place. The goal is to determine exactly which teams are eliminated. The problem is not as easy as many sports writers would have you believe, in part because the answer depends not only on the number of games won and left to play, but also on the schedule of remaining games. In the 1960's, Schwartz showed how to determine whether one particular team is eliminated using a maximum flow computation. This paper indicates that the problem is not as difficult as many mathematicians would have you believe. For each team i, let gi denote the number of games remaining. We prove that there exists a value W* such that team i is eliminated if and only if wi+gi<W*. Using this surprising fact, we can determine all eliminated teams in time proportional to a single maximum flow computation in a graph with n nodes; this improves upon the previous best known complexity bound by a factor of n.

Original languageEnglish (US)
Pages815-819
Number of pages5
StatePublished - 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'New property and a faster algorithm for baseball elimination'. Together they form a unique fingerprint.

Cite this