Matroids on Convex Geometries: Subclasses, Operations, and Optimization

Abstract

A matroid-like structure defined on a convex geometry, called a cg-matroid, was introduced by S. Fujishige, G. A. Koshevoy, and Y. Sano [Matroids on convex geometries (cg-matroids), Discrete Math. 307 (2007) 1936{1950]. In this paper, we continue the study of cg-matroids and extend the theory of cg-matroids. We give some characterizations of cg-matroids by axioms. Strict cg-matroids are a special subclass of cg-matroids which have nice properties. We define another subclass of cg-matroids, called co-strict cg-matroids, which also have good properties. Moreover, we consider operations on cg-matroids such as restriction and contraction. These operations are closely related to subclasses of cg-matroids. We also consider an optimization problem on cg-matroids, which reveals the relation between the greedy algorithm and cg-matroids.