Strong Algorithms for the Ordinal Matroid Secretary Problem

• 成果类型: Article
• 署名作者: Soto, Jose A.; Turkieltaub, Abner; Verdugo, Victor
• 署名单位: Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile; University of British Columbia; Universidad de O'Higgins
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.1083
• 发表日期: 2021
• 页码: 642-673
• 关键词: graphs; RIGIDITY

摘要

In the ordinal matroid secretary problem (MSP), candidates do not reveal numerical weights, but the decision maker can still discern if a candidate is better than another. An algorithm alpha is probability-competitive if every element from the optimum appears with probability 1/alpha in the output. This measure is stronger than the standard utility competitiveness. Our main result is the introduction of a technique based on forbidden sets to design algorithms with strong probability-competitive ratios on many matroid classes. We improve upon the guarantees for almost every matroid class considered in the MSP literature. In particular, we achieve probability-competitive ratios of 4 for graphic matroids and of 3 root 3 approximate to 5.19 for laminar matroids. Additionally, we modify Kleinberg's utility-competitive algorithm for uniform matroids in order to obtain an asymptotically optimal probability-competitive algorithm. We also contribute algorithms for the ordinal MSP on arbitrary matroids.