The 2-quasi-greedy algorithm for cardinality constrained matroid bases (Q1079134): Difference between revisions

The quasi-greedy algorithm is generalized to provide an efficient 2- quasi-greedy algorithm for a minimum weight base constrained to have a fixed number of elements from two disjoint sets. It is shown that optimal bases for adjacent states may not themselves be adjacent, however, optimal solutions for adjacent states can be found from information about the current base. Moreover, a further increase of efficiency is shown to be possible by jumping over certain adjacent states.