Breaking The Symmetry For The Matroid Secretary Problem

In the Matroid Secretary Problem (MSP), the elements of the ground set of a Matroid are revealed on-line one by one, each together with its value. An algorithm for the MSP is Matroid-Unknown if, at every stage of its execution: (i) it only knows the elements that have been revealed so far and their values, and (ii) it has access to an oracle for testing whether or not a any subset of the elements that have been revealed so far forms an independent set. An algorithm is Known-Cardinality if, in addition to (i) and (ii), it also knows, from the start, the cardinality of the ground set of the Matroid. The goal when designing algorithms for the MSP is to minimise the algorithm's Competitive-ratio, that is, the ratio of the optimal solution in the offline setting to the expectation of the value of the solution returned by the algorithm. The first Known-Cardinality algorithm for the MSP, by Babaioff et al. (2007), has a Competitive-ratio of O(log rho), and the latest, by Chakraborty and Lachish (2012), has a Competitive-ratio of O(sqrt log rho), where rho is the rank of the matroid. The square root competitive ratio is achieved using techniques that rely strongly on symmetry. In order to improve upon this result we develop a new technique that 'breaks the symmetry'. In this talk we will present both of the preceding techniques and explain how they are used to improve on the earlier results.