Trioid:: A generalization of matroid and the associated polytope - Kabadi, Santosh; Punnen, Abraham (Algorithmic Operations Research)

(untitled) (Preeminent Academic Facets Inc., 2011)
We consider a generalization of the well known greedy algorithm, called m-step greedy algorithm, where m elements are examined in each iteration. When m = 1 or 2, the algorithm reduces to the standard greedy algorithm. For m = 3 we provide a complete characterization of the independence system, called trioid, where the m-step greedy algorithm guarantees an optimal solution for all weight functions. We also characterize the trioid polytope and propose a generalization of submodular functions.