Matroid Secretary Conjecture

Let $M=(E,\mathcal I)$ be a finite matroid. The algorithm knows $E$ in advance and has access to an independence oracle for $M$. Each element $e\in E$ has a nonnegative weight

$$w(e)\in\mathbb R_{\ge 0}.$$

The weights are fixed in advance, but are unknown to the algorithm. The elements of $E$ are presented one at a time in a uniformly random order. When an element is revealed, the algorithm learns its weight and must decide immediately whether to select it. This decision cannot later be changed, and the elements selected so far must form an independent set of $M$.

For $S\subseteq E$, let

$$w(S)=\sum_{e\in S}w(e),$$

and write

$$\operatorname{OPT}(M,w) = \max_{I\in\mathcal I}w(I).$$

Conjecture. There exist an absolute constant $c\ge 1$ and an online algorithm such that, for every finite matroid $M$ and every choice of nonnegative weights, the algorithm selects an independent set $\operatorname{ALG}$ satisfying

$$\mathbb E[w(\operatorname{ALG})] \ge \frac{1}{c}\operatorname{OPT}(M,w).$$

The expectation is over the uniformly random arrival order and any internal randomness of the algorithm. Here $c$ is an absolute constant: It cannot depend on the rank or size of the matroid, or on the weights.

Equivalently, is there a constant-competitive algorithm for the matroid secretary problem?

Background. Babaioff, Immorlica, and Kleinberg introduced the matroid secretary problem and gave an $O(\log r)$-competitive algorithm for a matroid of rank $r$. They asked whether a constant-competitive algorithm exists for general matroids. Lachish later improved the general bound to $O(\log\log r)$, and Feldman, Svensson, and Zenklusen obtained another $O(\log\log r)$ algorithm.

This is the usual zero-information version of the problem: the weights may be assigned arbitrarily, while the order in which the elements appear is random. It is different from the random-assignment model, where an adversary chooses the weights but they are assigned randomly to the elements.