A connection between sports and matroids: how many teams can we beat? (Q1702129): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2557657806 / rank | |||
Normal rank |
Revision as of 20:18, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A connection between sports and matroids: how many teams can we beat? |
scientific article |
Statements
A connection between sports and matroids: how many teams can we beat? (English)
0 references
28 February 2018
0 references
In this well-written paper, the authors are motivated by the following question: Given an on-going sports competition, with each team having a current score and some matches left to be played, we ask whether it is possible for our distinguished team \(t\) to obtain a final standing with at most \(r\) teams finishing before \(t\). Baseball has the simplest scoring allocation, yet this question was shown to be difficult even in this situation in [\textit{A. J. Hoffman} and \textit{T. J. Rivlin}, in: Proceedings of the Princeton symposium on mathematical programming. Princeton University, Princeton, NJ, USA, 1967. Princeton, NJ: Princeton University Press. 391--401 (1970; Zbl 0231.90082)]. The authors in the paper under review focus mainly on approximation and fixed-parameter tractibility.
0 references
sports elimination problem
0 references
graph labelling
0 references
parameterized complexity
0 references
approximation
0 references
matroids
0 references
gammoids
0 references