×

New polyhedral and algorithmic results on greedoids. (English) Zbl 1462.90113

The paper defines a new class of greedoids named 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 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 [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.

MSC:

90C27 Combinatorial optimization
91A80 Applications of game theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baïou, M.; Barahona, F., Faster algorithms for security games on matroids, Algorithmica, 81, 3, 1232-1246 (2019) · Zbl 1422.91035 · doi:10.1007/s00453-018-0466-x
[2] Boyd, E.A.: A Combinatorial Abstraction of the Shortest Path Problem and Its Relationship to Greedoids, CAAM Technical Report, 30 pages (1988)
[3] Cunningham, WH, Optimal attack and reinforcement of a network, J. ACM (JACM), 32, 3, 549-561 (1985) · Zbl 0629.90034 · doi:10.1145/3828.3829
[4] Edmonds, J., Matroids and the greedy algorithm, Math. Program., 1, 1, 127-136 (1971) · Zbl 0253.90027 · doi:10.1007/BF01584082
[5] Helman, P.; Moret, BME; Shapiro, HD, An exact characterization of greedy structures, SIAM J. Discrete Math., 6, 274-283 (1993) · Zbl 0798.68061 · doi:10.1137/0406021
[6] Korte, B.; Lovász, L.; Pulleyblank, W., Greedoids—a structural framework for the greedy algorithm, Progress in Combinatorial Optimization, 221-243 (1984), London: Academic Press, London · Zbl 0547.05025 · doi:10.1016/B978-0-12-566780-7.50019-2
[7] Korte, B.; Lovász, L., Greedoids and linear objective functions, SIAM J. Algebr. Discrete Methods, 5, 2, 229-238 (1984) · Zbl 0538.05027 · doi:10.1137/0605024
[8] Korte, B.; Lovász, L.; Schrader, R., Greedoids (1991), Berlin: Springer, Berlin · Zbl 0733.05023 · doi:10.1007/978-3-642-58191-5
[9] Laszka, A., Szeszlér, D., Buttyán, L.: Game-theoretic Robustness of Many-to-one Networks. In: Proceedings of Game Theory for Networks: Third International ICST Conference, GameNets 2012, Vancouver, Canada, pp. 88-98. Springer, Berlin (2012) · Zbl 1268.91042
[10] Mao, H., A greedy algorithm for interval greedoids, Open Math., 16, 260-267 (2018) · Zbl 1391.90525 · doi:10.1515/math-2018-0026
[11] Schmidt, W., A characterization of undirected branching greedoids, J. Comb. Theory Ser. B, 45, 160-184 (1988) · Zbl 0646.05016 · doi:10.1016/0095-8956(88)90067-6
[12] Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics (2003), Berlin: Springer, Berlin · Zbl 1041.90001
[13] Szeszlér, D., Security games on matroids, Math. Program., 161, 1, 347-364 (2017) · Zbl 1366.91006 · doi:10.1007/s10107-016-1011-9
[14] Szeszlér, D.: Measuring graph robustness via game theory. In: Proceedings of 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, pp. 473-482 (2017)
[15] Szeszlér, D.: Optimality of the greedy algorithm in greedoids. In: Proceedings of 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, pp. 438-445 (2019)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.