New polyhedral and algorithmic results on greedoids (Q2220660)

The paper defines a new class of greedoids named \textit{local forest greedoids}, that includes both matroids and branching greedoids. The first result of the paper is a generalization of a fundamental Edmonds' classic theorem on the polytope spanned by incidence vectors of independent sets of a matroid. A generalization of an eqivalent formulation of this theorem to local forest greedoids is proved. The next part of the paper deals with the attacker-defender game named the Matroid Base Game. It is a two-player, zero sum game in which the Attacker chooses an element of the ground set of a given matroid and the Defender chooses a base of the same matroid. The payoff depends on both of their choices in such a way that it is favorable for the Attacker if his chosen element belongs to the base chosen by the Defender. In this paper, the authors further generalize the definition of the Matroid Base Game by replacing matroids with local forest greedoids and prove that some of the results of \textit{D. Szeszlér} [Math. Program. 161, No. 1--2 (A), 347--364 (2017; Zbl 1366.91006)] generalize to this case too. They also show that this more general framework is capable of handling and generalizing some further graph reliability metrics known from the literature beyond the ones already contained in the framework provided by the matroid base game. Finally, the paper analyses known results about the conditions under which the greedy algorithm is optimal on greedoids. The authors analyse in particular results of [\textit{B. Korte} et al., Greedoids. Berlin: Springer (1991; Zbl 0733.05023)] and identify some false claims there. These mistakes are pointed out and corrections are proposed and proved.