Persistency in combinatorial optimization problems on matroids |
| |
| Authors: | Katarína Cechlrov Vladimír Lacko |
| |
| Institution: | Katarína Cechlárová,Vladimír Lacko |
| |
| Abstract: | 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 
of the basic set 
of the matroid, where 
contain elements belonging to all optimum solutions; 
contain elements not belonging to any optimum solution; 
contain elements that belong to some but not to all optimum solutions. |
| |
| Keywords: | Matroid Greedy algorithm Base Matroid intersection problem Persistency |
| 本文献已被 ScienceDirect 等数据库收录！ |
