Matroids on convex geometries: subclasses, operations, and optimization (Q638783)

The purpose of this paper is to continue the study of convex geometry matroids (cg-matroids) and extend the theory of cg-matroids. A matroid-like structure defined on a convex geometry, called a cg-matroid, was introduced by \textit{S. Fujishige}, \textit{G. A. Koshevoy} and \textit{Y. Sano} [Discrete Math. 307, No. 15, 1936--1950 (2007; Zbl 1114.52018)]. The paper under review contains two generalizations of the results of authors mentioned. The one is that cg-matroids have good properties (exchange, augmentation, intersection properties), and the othe is that there are interesting subclasses (\(k\)-uniform, strict) of cg-matroids. The author gives some characterizations of cg-matroids by axioms. An example that shows that there are cg-matroids that are not strict cg-matroids, is presented. He defines another subclass of cg-matroids, called co-strict cg-matroids, which also have good properties. Moreover, the author considers operations on cg-matroids such as restriction and contraction. These operations are closely related to subclasses of cg-matroids. He also considers an optimization problem on cg-matroids, which reveals the relation between the greedy algorithms and cg-matroids. A general model for matroids and greedy algorithms is considered by \textit{U. Faigle} and \textit{S. Fujishige} [Math. Program. 119, No. 2 (A), 353--369 (2007; Zbl 1180.90268)]. Let \(M=(E,\mathcal{F};\mathcal{I})\) be a cg-matroid with the family set \(\mathcal{I}\) of independent sets, and \(w : E \to {\mathbb{R}}_{\geq 0}\) be a nonnegative weight function on \(E\). The author of the paper under review defines the maximum independent set problem as the following: \(P_{\max} (\mathcal{I}, w):\) maximize \(w(I)\) subject to \( I \in {\mathcal{I}}(M)\). He considers this problem more generally for hereditary systems on a convex geometry. \(\mathcal{F}\) - feasible ordering on closed set of convex geometry \((E,\mathcal{F})\) and natural weighting on \((E,\mathcal{F})\) as \(\mathcal{F}\) - feasible ordering \((e_1,\dots ,e_n )\) of \(E\) such that \(w(e_1) \geq \dots \geq w(e_n)\) are introduced. Theorem 6.6: Let \((E,\mathcal{F}; \mathcal{I})\) be a hereditary system on a convex geometry. Then \((E,\mathcal{F}; \mathcal{I})\) is a strict cg-matroid if and only if the greedy algorithm produces an optimal solution of \(P_{\max} (\mathcal{\mathcal I},w)\) for \((E,\mathcal{F}; \mathcal{I})\) with any natural weighting \(w\) on \((E,\mathcal{F})\). The author then gives some examples which show that the greedy algorithm fails for a strict cg-matroid with a non-natural weighting and also fails for a non-strict cg-matroid with a natural weighting. A number of examples and figures are provided to illustrate the basic definitions and theorems.