Strong Algorithms for the Ordinal Matroid Secretary Problem

Abstract

In the ordinal matroid secretary problem (MSP), candidates do not reveal numerical weights, but the decision maker can still discern if a candidate is better than another. An algorithm alpha is probability-competitive if every element from the optimum appears with probability 1/alpha in the output. This measure is stronger than the standard utility competitiveness. Our main result is the introduction of a technique based on forbidden sets to design algorithms with strong probability-competitive ratios on many matroid classes. We improve upon the guarantees for almost every matroid class considered in the MSP literature. In particular, we achieve probability-competitive ratios of 4 for graphic matroids and of 3 root 3 approximate to 5.19 for laminar matroids. Additionally, we modify Kleinberg's utility-competitive algorithm for uniform matroids in order to obtain an asymptotically optimal probability-competitive algorithm. We also contribute algorithms for the ordinal MSP on arbitrary matroids.