Pseudomatroids (Q1109779): Difference between revisions

In this paper the authors describe a generalization of a matroid called a pseudomatroid. These objects are defined in terms of the optimality of a certain generalized greedy algorithm. Like matroids, they can be defined in several different ways. The independent set axiomatization is as follows. If E is a finite set and \({\mathcal I}\) is a non-empty set of subsets of E, then (E,\({\mathcal I})\) is a pseudomatroid if and only if the following conditions hold whenever I and J are members of \({\mathcal I}\) and \(i\in I-J:\) (i) either \(J\cup \{j,k\}\in {\mathcal I}\) for some k in I-J, or \((J\cup j)-k\in {\mathcal I}\) for some k in J-I; and (ii) either \(I- \{j,k\}\in {\mathcal I}\) for some k in I-J, or \((I\cup k)-j\in {\mathcal I}\) for some k in J-I. The authors develop a theory of duality and minors for pseudomatroids. They also introduce a rank function for these objects, give a polyhedral characterization of them, and show that such objects include the generalized matroids of A. Frank. Their stated aim is to provide a unified framework for many problems in combinatorial optimization. Although one may anticipate there being some link between pseudomatroids and greedoids, the authors admit they are unable to find one.