REWARDING MAPS - ON GREEDY OPTIMIZATION OF SET-FUNCTIONS

Given a set function, that is, a map f:P(E) --> (R) over bar = R boole an OR (-infinity) from the set P(E) of subsets of a finite set E into the reals including -infinity, the standard greedy algorithm (GA) for optimizing f starts with the empty set and then proceeds by enlarging this set greedily, element by element. A set function f is said to be tractable if in this way a sequence x(0) = empty set, x(1),...,x(N) = E (N = #E) of subsets with max(f) is an element of {f(x(0)), f(x(1)),. ..,f(x(N))} will always be found. In this note, we will reinterpret an d transcend the traditions of classicaI GA-theory (cf., e.g., KLS) b y establishing necessary and sufficient conditions for a set function f not just to be tractable as it stands, but to give rise to a whole f amily of tractable set functions f(eta):P(E) --> (R) over bar:x --> f( x) + Sigma(e is an element of x)eta(e), where eta runs through all rea l valued weighting schemes eta:E --> R, in which case f 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 f such that f((i)):P(E) --> (R) over bar:x --> GRAPHICS is rewarding for every i = 1,..., N, and matroidal maps, t hat is, set functions f such that for every eta:E --> R and every f(et a)-greedy sequence x(0),x(1),...,x(N) as above, one has max(f(eta)) = f(eta)(x(i)) for the unique i is an element of {0,...,N} with f(eta)(x (0)) < f(eta)(x(1))<...< f(eta)(x(i))greater than or equal to f(eta)(x (i+1)). (C) 1995 Academic Press, Inc.