A connection between sports and matroids: how many teams can we beat? (Q1702129): Difference between revisions

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.