Matroid kernel

Let $$M_1=(S,{\mathcal I}_1)$$ and $$M_2=(S,{\mathcal I}_2)$$ be two matroids on the same ground set S, and let $$\prec_1$$ and $$\prec_2$$ be partial orders on S. A common independent set $$X \in {\mathcal I}_1 \cap {\mathcal I}_2$$ is an $$M_1M_2$$ -kernel if for each $$s \in S\setminus X$$ at least one of the following two possibilities holds:

• $$X+s \notin {\mathcal I}_1$$ , and $$t \preceq_1 s$$ whenever $$X-t+s \in {\mathcal I}_1$$ ,
• $$X+s \notin {\mathcal I}_2$$ , and $$t \preceq_2 s$$ whenever $$X-t+s \in {\mathcal I}_2$$ .

Fleiner proved the following theorem.

Theorem. An $$M_1M_2$$ -kernel always exists, and it can be found in polynomial time using rank oracles for the matroids. In addition, a minimum cost $$M_1M_2$$ -kernel can be found using the ellipsoid method.