Matroids on Convex Geometries: Subclasses, Operations, and Optimization

  • Yoshio Sano

    Kyoto University, Japan

Abstract

A matroid-like structure de ned 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 de ne 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.

Cite this article

Yoshio Sano, Matroids on Convex Geometries: Subclasses, Operations, and Optimization. Publ. Res. Inst. Math. Sci. 47 (2011), no. 3, pp. 671–703

DOI 10.2977/PRIMS/48