Matroids on convex geometries: subclasses, operations, and optimization
type: Item
instance of: scholarly article
title: Matroids on convex geometries: subclasses, operations, and optimization
zbMATH Open document ID: 1253.05057
DOI: 10.2977/PRIMS/48
author: Yoshio Sano
published in: Publications of the Research Institute for Mathematical Sciences, Kyoto University
publication date: 2011-09-14T00:00:00Z
review text: 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}…
reviewed by: Nikolaj M. Glazunov
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 52B40
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 5947481
zbMATH Keywords: convex geometry matroids
zbMATH Keywords: independent set
zbMATH Keywords: spanning set
MaRDI profile type: Publication
cites work: Extreme point axioms for closure spaces
cites work: Matroids on partially ordered sets
cites work: The theory of convex geometries
cites work: Q4414632
cites work: A general model for matroids and the greedy algorithm
cites work: Submodular functions and optimization.
cites work: Matroids on convex geometries (cg-matroids)
cites work: Greedoids
cites work: Q3135082
cites work: Poset matching---a distributive analog of independent matching
cites work: Rank functions of strict cg-matroids
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: An intersection theorem for supermatroids
cites work: Q4111952
cites work: On the Abstract Properties of Linear Dependence
full work available at URL: https://doi.org/10.2977/prims/48
OpenAlex ID: W2092136115
description: scientific article; zbMATH DE number 5947481