A connection between sports and matroids: how many teams can we beat?
type: Item
instance of: scholarly article
title: A connection between sports and matroids: how many teams can we beat?
zbMATH Open document ID: 1406.05015
author: Ildikó Schlotter
author: Katarina Cechlárová
published in: Algorithmica
publication date: 2018-02-28T00:00:00Z
full work available at URL: mbc.pdf
review text: 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.
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 52B40
zbMATH DE Number: 6844604
zbMATH Keywords: sports elimination problem
zbMATH Keywords: graph labelling
zbMATH Keywords: parameterized complexity
zbMATH Keywords: approximation
zbMATH Keywords: matroids
zbMATH Keywords: gammoids
reviewed by: Kelly J. Pearson
MaRDI profile type: Publication
OpenAlex ID: W2557657806
cites work: Upper and lower degree-constrained graph orientation with minimum penalty
cites work: Q4941919
cites work: Refining the complexity of the sports elimination problem
cites work: Planar orientations with low out-degree and compaction of adjacency matrices
cites work: Q5315023
cites work: Degree-constrained orientations of embedded graphs
cites work: Fundamentals of parameterized complexity
cites work: Lattice structures from planar graphs
cites work: Q4170745
cites work: Q4198056
cites work: Clustering to minimize the maximum intercluster distance
cites work: A fast algorithm for the generalized parametric minimum cut problem and applications
cites work: The structure and complexity of sports elimination numbers
cites work: On the degrees of the vertices of a directed graph
cites work: Parameterized Complexity of Induced H-Matching on Claw-Free Graphs
cites work: Q5639561
cites work: The new FIFA rules are hard: Complexity aspects of sports competitions.
cites work: The computational complexity of the elimination problem in generalized sports competitions
cites work: Combinatorial optimization. Networks and matroids
cites work: Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
cites work: Q2941638
cites work: This House Proves that Debating is Harder than Soccer
cites work: Applications of Menger's graph theorem
cites work: Minimum perfect bipartite matchings and spanning trees under categorization
cites work: Baseball playoff eliminations: An application of linear programming. Erratum
cites work: Possible Winners in Partially Completed Tournaments
cites work: A new property and a faster algorithm for baseball elimination
DOI: 10.1007/S00453-016-0256-2
description: scientific article; zbMATH DE number 6844604