Closure in Independence Systems

The set of feasible solutions of a discrete optimization problem can, in many cases, be represented as an independence system, or hereditary system of sets. It is often the case that this system has some structure which may be exploited in the solution of the problem. For example, in the case of a matroid a “greedy algorithm” can be used; this situation, however, occurs rarely in practice. We investigate here the abstract structure of independence systems using concepts from matroid theory, in particular analogues of matroid closure. Two functions are defined which coincide with the ususal closure operator if the independence system is a matroid, and for each of these functions an axiomatic characterization is given. In each case this consists of a weakened form of one of the matroid closure axioms with the other three remaining unchanged. Finally, duality is considered and this leads to characterizations, in terms of closure operators and paintings, of those independence systems where all bases have the same cardinality: these include the “Travelling Salesman” and “Acyclic Subgraph” independence systems.