Abstract: | Given a set function, that is, a map ƒ:
(E) →
{−∞} from the set
(E) of subsets of a finite set E into the reals including −∞, the standard greedy algorithm (GA) for optimizing ƒ starts with the empty set and then proceeds by enlarging this set greedily, element by element. A set function ƒ is said to be tractable if in this way a sequence x0 , x1, . . ., xN E (N #E) of subsets with max(ƒ) {ƒ(x0), ƒ(x1), . . ., ƒ(xN)} will always be found. In this note, we will reinterpret and transcend the traditions of classical GA-theory (cf., e.g., KLS]) by establishing necessary and sufficient conditions for a set function ƒ not just to be tractable as it stands, but to give rise to a whole family of tractable set functions ƒ(η) :
(E) →
: x ƒ(x) + Σe xη(e), where η runs through all real valued weighting schemes η : E →
, in which case ƒ will be called rewarding. In addition, we will characterize two important subclasses of rewarding maps, viz. truncatably rewarding (or well-layered) maps, that is, set functions ƒ such that formula] is rewarding for every i = 1, . . ., N, and matroidal maps, that is, set functions ƒ such that for every η : E →
and every ƒeta-greedy sequence x0, x1, . . ., xN as above, one has max(ƒη) = ƒη(xi) for the unique i {0, . . ., N} with ƒη(x0) < ƒη(x1) < ··· < ƒη(xi) ≥ ƒη(xi + 1). |