A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

• 成果类型: Article
• 署名作者: Feldman, Moran; Svensson, Ola; Zenklusen, Rico
• 署名单位: Open University Israel; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0876
• 发表日期: 2018
• 页码: 638-650

摘要

Only recently, progress has been made in obtaining o(log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a O((log(rank))(1/2))-competitive procedure, and Lachish (2014) later presented a O(log log(rank))-competitive algorithm. Both these algorithms and their analyses are very involved, which is also reflected in the extremely high constants in their competitive ratios. Using different tools, we present a considerably simpler O(log log(rank))-competitive algorithm for the matroid secretary problem. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms that are easy to analyze. Because of the simplicity of our procedure, we are also able to vastly improve on the hidden constant in the competitive ratio.