Strong Algorithms for the Ordinal Matroid Secretary Problem
share
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(√(ρ/ρ)) probability-competitive algorithm for uniform matroids of rank ρ based on Kleinberg's 1+O(√(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(ρ) probability-competitive algorithm and an O(ρ) ordinal-competitive algorithm, a weaker notion of competitiveness but stronger than the utility variant. These are based on the O(ρ) utility-competitive algorithm by Feldman et al. [SODA 2015].
READ FULL TEXT