Abstracts
Abstract
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.
Keywords:
- Matroid,
- independence system,
- greedy algorithm,
- trioid,
- combinatorial optimization
Download the article in PDF to read it.
Download