Strong Algorithms for the Ordinal Matroid Secretary Problem

Abstract

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 $\alpha$ probability-competitive if every element from the optimum appears with probability $1/\alpha$ 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 \rho /\rho })$ probability-competitive algorithm for uniform matroids of rank $\rho$ based on Kleinberg's $1+O(\sqrt{1/\rho })$ utility-competitive algorithm [SODA 2005] for that class. Our second contribution are algorithms for the ordinal MSP on arbitrary matroids of rank $\rho$. We devise an $O(\log \rho )$ probability-competitive algorithm and an $O(\log \log \rho )$ ordinal-competitive algorithm, a weaker notion of competitiveness but stronger than the utility variant. These are based on the $O(\log \log \rho )$ utility-competitive algorithm by Feldman et al.~[SODA 2015].

A preliminary version appeared at ACM-SIAM SODA 18