(Nazarbayev University School of Science and Technology, 2016) Myrzakul, Zhanbota
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)?