Return to Colloquia & Seminar listing
When is a Team Eliminated?
Student-Run Research| Speaker: | Chip Martel, CS, UC Davis |
| Location: | 593 Kerr |
| Start time: | Mon, Oct 9 2000, 2:10PM |
Description
Joint work with Dan Gusfield CS UCD. Identifying the teams that are
already eliminated from contention for first place of a sports league, is
a classic problem that has been widely used to illustrate the application
of linear programming and network flow. In the classic setting each game
is played between two teams and the first place goes to the team with the
greatest total wins. Recently, two papers cite{KW98} and cite{AH}
detailed a surprising structural fact in the classic. setting: At any
point in the season, there is a computable threshold $W$ such that a team
is eliminated (has no chance to win or tie for first place) if and only if
it cannot win $W$ or more games. They used this threshold to speed up the
identification of eliminated teams. In both papers, the proofs of the
existence of a threshold are tied to the computational methods used to
find it.
In this paper we show that thresholds exist for a wide range of
elimination problems (including European Football and greatly generalizing
the classical setting), via a simpler proof not connected to any
particular computational method; we resolve the more refined issue (in the
classic setting) of which teams have a chance to be the {it strict}
winner of the most games; examine these issues in the context of
multi-division leagues with playoffs and wildcards; and establish
NP-hardness results for certain elimination questions.