Strong Algorithms for the Ordinal Matroid Secretary Problem

In the ordinal Matroid Secretary Problem (MSP), elements from a weighted matroid are presented in random order to an algorithm that must incrementally select a large weight independent set. However, the algorithm can only compare pairs of revealed elements without using its numerical value. An algorithm is $α$ probability-competitive if every element from the optimum appears with probability $1/α$ in the output. We present a technique to design algorithms with strong probability-competitive ratios, improving the guarantees for almost every matroid class considered in the literature: e.g., we get ratios of 4 for graphic matroids (improving on $2e$ by Korula and Pál [ICALP 2009]) and of 5.19 for laminar matroids (improving on 9.6 by Ma et al. [THEOR COMPUT SYST 2016]). We also obtain new results for superclasses of $k$ column sparse matroids, for hypergraphic matroids, certain gammoids and graph packing matroids, and a $1+O(\sqrt{\log ρ/ρ})$ probability-competitive algorithm for uniform matroids of rank $ρ$ based on Kleinberg's $1+O(\sqrt{1/ρ})$ utility-competitive algorithm [SODA 2005] for that class. Our second contribution are algorithms for the ordinal MSP on arbitrary matroids of rank $ρ$. We devise an $O(\log ρ)$ probability-competitive algorithm and an $O(\log\log ρ)$ ordinal-competitive algorithm, a weaker notion of competitiveness but stronger than the utility variant. These are based on the $O(\log\log ρ)$ utility-competitive algorithm by Feldman et al.~[SODA 2015].