Trioid: A generalization of matroid and the associated polytope

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.

Citation

Manuscript, Department of Mathematics, Simnon Fraser University Surrey, 2009

Article

Download

View Trioid: A generalization of matroid and the associated polytope