During the last twenty years, a lot of research was conducted on the sport elimination problem: Given a sports league and its remaining matches, we have to decide whether a given team can still possibly win the competition, i.e., place first in the league at the end. Previously, the computational complexity of this problem was investigated only for games with two participating teams per game. In this paper we consider Debating Tournaments and Debating Leagues in the British Parliamentary format, where four teams are participating in each game. We prove that it is NP-hard to decide whether a given team can win a Debating League, even if at most two matches are remaining for each team. This contrasts settings like football where two teams play in each game since there this case is still polynomial time solvable. We prove our result even for a fictitious restricted setting with only three teams per game. On the other hand, for the common setting of Debating Tournaments we show that this problem is fixed parameter tractable if the parameter is the number of remaining rounds @math . This also holds for the practically very important question of whether a team can still qualify for the knock-out phase of the tournament and the combined parameter @math where @math denotes the threshold rank for qualifying. Finally, we show that the latter problem is polynomial time solvable for any constant @math and arbitrary values @math that are part of the input.
In 1966, Schwartz @cite_22 proved that using flow networks it can be decided in polynomial time whether a baseball team can still win a baseball league. In baseball the winner of a game wins a single point and the looser gets zero points, there is no tie. McCormick @cite_9 generalized this result by giving a polynomial time algorithm which allowed to fix a number of losses for the team that is supposed to win the league. Wayne @cite_0 characterised all teams of a baseball league which can still win the league by giving a threshold value for the number of points and the number of matches a team must have to be able to win the league. He further gave a polynomial time algorithm to compute this threshold. This result was later improved by Gusfield and Martel @cite_8 who gave thresholds for a bigger set of possible outcomes of the matches. For baseball leagues they gave a faster algorithm to determine the threshold and further allowed leagues with multiple divisions and wild-cards @cite_8 .
@cite_0 @cite_9 @cite_22 @cite_8
1980618969 2117135110 2077123737 1555156751
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. Chen (1994) develops an attractive variant of the classical problem of preemptively scheduling independent jobs with release dates and due dates. Chen suggests that in practice one can often pay to reduce the processing requirement of a job. This leads to two parametric max flow problems. Serafini (1996) considers scheduling independent jobs with due dates on multiple machines, where jobs can be split among machines so that pieces of a single job can execute in parallel. Minimizing the maximum tardiness again gives a parametric max flow problem. A third problem of this type is deciding how many more games a baseball team can lose part way through a season without being eliminated from finishing first (assuming a best possible distribution of wins and losses by other teams). A fourth such problem is an extended selection problem of (1995a), where we want to discount the costs of "tree-structured" tools as little as possible to be able to process all jobs at a profit. It is tempting to try to solve these problems with the parametric push-relabel max flow methods of (GGT) (1989). However, all these applications appear to violate the conditions necessary to apply GGT. We extend GGT in three ways that allow it to be applied to all four of the above applications. We also consider some other applications where these ideas apply. Our extensions to GGT yield faster algorithms for all these applications. 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 [W], [AEHO] detailed a surprising structural fact in the classic setting: At any point in the season, there is a computable threshold W such that for any team i , i is eliminated (has no chance to win or tie for first place) if and only if i 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.