Optimization of convex geometries: component quadratic and general

Abstract

In this Capstone Project, we worked with a class of closure systems called convex geometries, which are closure systems with a closure operator that satisfies the anti-exchange property. We first looked at the result of optimization algorithm of component quadratic systems, which are discussed in [4], and reproved it for the case of convex geometries. We then investigated the following question: if a convex geometry is given by a set of implications, is it possible to find its optimum basis in polynomial time when the convex geometry does not have particular properties (for instance, not component quadratic)?