A greedy algorithm for convex geometries

✍ Scribed by Kenji Kashiwabara; Yoshio Okamoto

• Book ID: 104294093
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 308 KB
• Volume: 131
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00467-5

✦ Synopsis

Convex geometries are closure spaces which satisfy anti-exchange property, and they are known as dual of antimatroids. We consider functions deÿned 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 uger (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.