Online Matroid Intersection: Beating Half for Random Arrival

Guru Guruganesh, Sahil Singla

For two matroids ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ defined on the same ground set $E$, the online matroid intersection problem is to design an algorithm that constructs a large c…