2
$\begingroup$

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.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.