Greedy algorithm compatibility and heavy-set structures (Q1193543)

The paper considers a relation between the set structure called strong greedoid and the possibility of using the greedy algorithm for finding an optimal solution. A strong greedoid is defined as a set system \((E,{\mathcal E})\) with the following properties: (1) \(\varnothing\in{\mathcal E}\); (2) if \(A\in{\mathcal E}\) and \(A\neq\varnothing\) then there exists \(a\in A\) with \(A-\{a\}\in{\mathcal E}\); (3) if \(X,Y\in{\mathcal E}\) and \(X=Y+1\) then there exists \(x\in X-Y\) with \(Y\cup\{x\}\in{\mathcal E}\). It is shown that every strong greedoid is greedy algorithm compatible, that means a greedy algorithm chooses a sequence of sets \(\varnothing\subset A_ 1\subset\cdots\subset A_ n\) where \(A_ r\) is a heaviest independent set of cardinality \(r\) with respect to a given weight function. Moreover, any sequence of heaviest sets of a given strong greedoid can be obtained by the greedy algorithm.