The Matroid Secretary Problem

Abstract

We study a fundamental topic in online decision-making called the matroid secretary problem. In this problem, elements of a matroid arrive in uniformly random order, and reveal their weights upon arrival. After learning an element’s weight, we must make an immediate and irrevocable decision on whether or not to accept the current element. The objective is to accept an independent set whose weight is comparable to the weight of the max-weight-bases of the matroid. Babaio↵ et al. (2007) conjectured that there exists an algorithm that achieves a competitive ratio of 1/e for all matroid constraints. This conjecture is still open. There have been many advances in the positive direction, including constantcompetitive algorithms for smaller subclasses of matroids. However, the extendability of these algorithms to the general setting has not been studied. In this work, we consider algorithms in limited computational models. We focus on two particular families of algorithms, namely partition matroids and greedy algorithms with limited memory, and prove that no algorithm of these types can be constant-competitive for the general matroid setting.