A new property and a faster algorithm for baseball elimination

Research output: Contribution to journalArticle

17 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)
Pages (from-to)223-229
Number of pages7
JournalSIAM Journal on Discrete Mathematics
Volume14
Issue number2
DOIs
StatePublished - Feb 1 2001

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Combinatorial optimization
  • Network flow

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

  • Cite this