A Simple O (1oglog (rank))-competitive algorithm for the matroid secretary problem

Only recently progress has been made in obtaining o (1og (rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a O (√log (rank))-competitive procedure, and Lachish (2014) recently presented a O (1oglog (rank))-competitive algorithm. Both algorithms aie involved with complex analyses. Using different tools, we present a considerably simpler O (1oglog (rank))-competitive algorithm. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. We are also able to vastly improve on the hidden constant in the competitive ratio.