2018/02/06 by Soto, José A., Turkieltaub, Abner, Verdugo, Victor · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1802.01997
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(√(log ρ/ρ)) 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(log ρ) probability-competitive algorithm and an O(loglog ρ) ordinal-competitive algorithm, a weaker notion of competitiveness but stronger than the utility variant. These are based on the O(loglog ρ) utility-competitive algorithm by Feldman et al.~[SODA 2015].