A greedy algorithm for convex geometries

AbstractConvex geometries are closure spaces which satisfy anti-exchange property, and they are known as dual of antimatroids. We consider functions defined on the sets of the extreme points of a convex geometry. Faigle–Kern (Math. Programming 72 (1996) 195–206) presented a greedy algorithm to linear programming problems for shellings of posets, and Krüger (Discrete Appl. Math. 99 (2002) 125–148) introduced b-submodular functions and proved that Faigle–Kern's algorithm works for shellings of posets if and only if the given set function is b-submodular. We extend their results to all classes of convex geometries, that is, we prove that the same algorithm works for all convex geometries if and only if the given set function on the extreme sets is submodular in our sense