Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  This House Proves that Debating is Harder than Soccer

Neumann, S., & Wiese, A. (2016). This House Proves that Debating is Harder than Soccer. Retrieved from http://arxiv.org/abs/1605.03063.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:1605.03063.pdf (Preprint), 376KB
Name:
arXiv:1605.03063.pdf
Beschreibung:
File downloaded from arXiv at 2016-07-13 12:51
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Neumann, Stefan1, Autor
Wiese, Andreas2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Computational Complexity, cs.CC
 Zusammenfassung: 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 $k$. 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 $k + b$ where $b$ denotes the threshold rank for qualifying. Finally, we show that the latter problem is polynomial time solvable for any constant $k$ and arbitrary values $b$ that are part of the input.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2016-05-102016
 Publikationsstatus: Online veröffentlicht
 Seiten: 18 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1605.03063
URI: http://arxiv.org/abs/1605.03063
BibTex Citekey: NeumannarXiv2016
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden: ausblenden:
Projektname : ERC Grant Agreement
Grant ID : 340506
Förderprogramm : European Unions Seventh Framework Programme (FP/2007-201)
Förderorganisation : Eurpean Research Council

Quelle

einblenden: