Matroid optimization with the interleaving of two ordered sets (Q793743)

The paper deals with the minimum weight basis B of a matroid on E; the ordering of E may vary, but the orderings of a subset R of E and of \(W=E\backslash R\) must remain fixed. It is shown that E consists of (i), (ii) elements which are never (resp. always) in B, and (iii) disjoint pairs \(\{\) r,\(w\}\) such that \(r\in R\), \(w\in W\), \(\min(r,w)\in B\) and \(\max(r,w)\not\in B.\) Applications in economics and to the matroid selection problem (find the minimum weight basis of E containing exactly q elements of R) are described. The algorithmic efficiency of various implementations of the results are discussed.