The 2-quasi-greedy algorithm for cardinality constrained matroid bases

AbstractThe quasi-greedy algorithm, as proposed by Glover and Klingman [8], efficiently solves minimum weight spanning tree problems with a fixed (or bounded) number of edges incident to a specified vertex. As observed in [8], the results carry through to general matroid problems (where a base contains a bounded number of elements from a specified set). We extend this work to provide an efficient 2-quasi-greedy algorithm where a minimum weight base is constrained to have a fixed number of elements from two disjoint sets.Our main results show that optimal bases for adjacent states may not themselves be adjacent. However, optimal solutions for adjacent states may be identified solely from information available in the current base, yielding a method whose efficiency rivals that of the quasi-greedy method. We also give theorems making it possible to jump over certain adjacent states, further increasing efficiency