Matroids on convex geometries: subclasses, operations, and optimization
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.
- A general model for matroids and the greedy algorithm
- An intersection theorem for supermatroids
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Extreme point axioms for closure spaces
- Greedoids
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 1953186 (Why is no real title available?)
- Matroids on convex geometries (cg-matroids)
- Matroids on partially ordered sets
- On the Abstract Properties of Linear Dependence
- Poset matching---a distributive analog of independent matching
- Rank functions of strict cg-matroids
- Submodular functions and optimization.
- The theory of convex geometries
This page was built for publication: Matroids on convex geometries: subclasses, operations, and optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638783)
