Persistency in combinatorial optimization problems on matroids Original Research Article

Optimization problems on matroids are generalizations of such important combinatorial optimization problems like the problem of minimum spanning tree of a graph, the bipartite matching problem, flow problems, etc. We analyze algorithms for finding the maximum weight independent set of a matroid and for finding a maximum cardinality intersection of two matroids and extend them to obtain the so-called “persistency” partition EAll,ENone,ESome of the basic set E of the matroid, where EAll contain elements belonging to all optimum solutions; ENone contain elements not belonging to any optimum solution; ESome contain elements that belong to some but not to all optimum solutions.