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
1515766120 1980618969 1555156751 2129219909
The "baseball elimination problem" is a classic problem which has already been considered from the computational point of view in the 1960's. At some stage of the baseball season, there is a set of games which have already been played and there is another set of remaining games. The problem consists in determining for a given team whether or not they are already "eliminated", i.e., whether they can no longer become champions. Early solutions proposed a network flow approach which resulted in polynomial time algorithms. The interest in this kind of elimination problem was recently revived by Wayne [4] who proved an interesting threshold property which allows one to compute all eliminated teams simultaneously. Namely, there is a constant W* such that a team is eliminated if and only if it can no longer obtain W* or more points. Wayne also describes an algorithm for computing the threshold W* in polynomial time. Gusfield and Maxtel [2] have generalized the proof of the existence of a threshold to a more general setting which includes European football, where the "3-point-rule" is in effect, i.e., 3 points are awarded for a win and 1 point is awarded for a tie. In this paper, we show that determining the elimination of a European football team under the 3-point-rule is NP-complete. As a consequence, the generalized threshold result of Gusfield and Mairtel is of no use for the European football system since computing the corresponding threshold value is hard if P # NP. We also show that the elimination problem is still NP-complete if all teams have at most three remaining games each while the problem can be solved in polynomial time if each team has at most two remaining games. 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. 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. In this paper we consider the problem of maximizing the number of supported connections in arbitrary wireless networks where a transmission is supported if and only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. The aim is to choose transmission powers for each connection so as to maximize the number of connections for which this threshold is met. We believe that analyzing this problem is important both in its own right and also because it arises as a subproblem in many other areas of wireless networking. We study both the complexity of the problem and also present some game theoretic results regarding capacity that is achieved by completely distributed algorithms. We also feel that this problem is intriguing since it involves both continuous aspects (i.e. choosing the transmission powers) as well as discrete aspects (i.e. which connections should be supported). Our results are: ldr We show that maximizing the number of supported connections is NP-hard, even when there is no background noise. This is in contrast to the problem of determining whether or not a given set of connections is feasible since that problem can be solved via linear programming. ldr We present a number of approximation algorithms for the problem. All of these approximation algorithms run in polynomial time and have an approximation ratio that is independent of the number of connections. ldr We examine a completely distributed algorithm and analyze it as a game in which a connection receives a positive payoff if it is successful and a negative payoff if it is unsuccessful while transmitting with nonzero power. We show that in this game there is not necessarily a pure Nash equilibrium but if such an equilibrium does exist the corresponding price of anarchy is independent of the number of connections. We also show that a mixed Nash equilibrium corresponds to a probabilistic transmission strategy and in this case such an equilibrium always exists and has a price of anarchy that is independent of the number of connections. This work was supported by NSF contract CCF-0728980 and was performed while the second author was visiting Bell Labs in Summer, 2008.