# Algorithms for parametric matroid optimization

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.