摘要

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. We study the computational complexity of this problem, addressing it both from the viewpoint of parameterized complexity and of approximation. We focus on a special case equivalent to finding a maximal induced subgraph of a given graph G that admits an orientation where the in-degree of each vertex is upper-bounded by a given function. We obtain a approximation for this problem based on an asymptotically optimal approximation we present for a certain matroid problem in which we need to cover a base of a matroid by picking elements from a set family.

  • 出版日期2018-1