Let $M$ be a rank $r$ matroid with basis set $\mathcal{B}$ and an independence oracle. Given a linear function $w_e$ on each element $e$ of the matroid, we want to find the minimum weight basis for each $\lambda$. That is, for each $\lambda$, we want to find $\arg\min_{B\in \mathcal{B}} \sum_{e\in B}w_e(\lambda)$. As $\lambda$ varies, there can be at most $O(n r^{1/3})$ different basis in the output [1].
What is the fastest algorithm that output all such sets?
[1] Dey, T. K., Improved bounds for planar (k)-sets and related problems, Discrete Comput. Geom. 19, No. 3, 373-382 (1998). ZBL0899.68107.
