Title :
O(log log Rank) Competitive Ratio for the Matroid Secretary Problem
Author_Institution :
Dept. of Comput. Sci. & Inf. Syst., Univ. of London, London, UK
Abstract :
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 called Matroid-Unknown if, at every stage of its execution, it only knows (i) the elements that have been revealed so far and their values and (ii) an oracle for testing whether or not a subset the elements that have been revealed so far forms an independent set. An algorithm is called Known-Cardinality if it knows (i), (ii) and also knows from the start the cardinality n of the ground set of the Matroid. We present here a Known-Cardinality algorithm with a competitive-ratio of order log log the rank of the Matroid. The prior known results for a OC algorithm are a competitive-ratio of log the rank of the Matroid, by Babaioff et al. (2007), and a competitive-ratio of square root of log the rank of the Matroid, by Chakraborty and Lachish (2012).
Keywords :
combinatorial mathematics; competitive algorithms; computational complexity; matrix algebra; set theory; Known-Cardinality algorithm; Matroid-Unknown; O(log log Rank) competitive ratio; matroid secretary problem; oracle; order log log; Algorithm design and analysis; Approximation algorithms; Computer science; Data preprocessing; Flyback transformers; Optimized production technology; Testing; Competitive-Ratio; Matroid; Secretary;
Conference_Titel :
Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on
Conference_Location :
Philadelphia, PA
DOI :
10.1109/FOCS.2014.42
