New polyhedral and algorithmic results on greedoids
成果类型：
Article
署名作者：
Szeszler, David
署名单位：
Budapest University of Technology & Economics
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01427-7
发表日期：
2021
页码：
275-296
关键词：
摘要：
We present various new results on greedoids. We prove a theorem that generalizes an equivalent formulation of Edmonds' classic matroid polytope theorem to local forest greedoids-a class of greedoids that contains matroids as well as branching greedoids. We also describe an application of this theorem in the field of measuring the reliability of networks by game-theoretical tools. Finally, we prove new results on the optimality of the greedy algorithm on greedoids and correct some mistakes that have been present in the literature for almost 3 decades.