No label defined (Q4038320)

The paper considers the following classical problem: for a given family J of admissible subsets of a discrete set \(S\), and a given weight function \(w: 2^ s\to R^ +\), find an admissible set of maximum weight. As is well-known, the ``greedy'' algorithm (choose the heaviest element at each step, provided that the resulting set is still admissible), produces an optimal set iff the underlying structure is a matroid. For ``defective independence systems'' (that are obtained from matroids by substituting the augmentation axiom with an exchange axiom), the ``greedy'' algorithm is in general suboptimal. The main result of the paper, however, is that in certain cases such an algorithm provides at least a subset of a maximum weight admissible set. More precisely, an ``exchange index'' \(q\) is defined as follows: \(q=\max\{\min| Y|: (A\cup x)-Y\in J;\;\forall\;A\in J,\;\forall x\in S-A\}\). Then, the main result of the paper reads as follows: the ``greedy'' algorithm performs the ``right'' choice until the element to be inserted into the solution has weight \(w(x)\geq w(X)\), for any \(X\) of cardinality \(q\), whose elements are chosen from the elements of \(S\), that have not been considered for possible insertion in the previous steps. Though not reported in the paper, it can be shown that such results can be somewhat extended to ``defective reduction systems'', that are obtained from ``greedoids'', by substituting the augmentation axiom with a weaker exchange axiom.