@inproceedings{fdc8351a47674602a381fd88cba356d2,
title = "Formal Barriers to Simple Algorithms for the Matroid Secretary Problem",
abstract = "Babaioff et al. [4] introduced the matroid secretary problem in 2007, a natural extension of the classic single-choice secretary problem to matroids, and conjectured that a constant-competitive online algorithm exists. The conjecture still remains open despite substantial partial progress, including constant-competitive algorithms for numerous special cases of matroids, and an O(log log rank ) -competitive algorithm in the general case. Many of these algorithms follow principled frameworks. The limits of these frameworks are previously unstudied, and prior work establishes only that a handful of particular algorithms cannot resolve the matroid secretary conjecture. We initiate the study of impossibility results for frameworks to resolve this conjecture. We establish impossibility results for a natural class of greedy algorithms and for randomized partition algorithms, both of which contain known algorithms that resolve special cases.",
keywords = "Graph theory, Greedy algorithms, Matroids, Optimal stopping theory, Secretary problem",
author = "Maryam Bahrani and Hedyeh Beyhaghi and Sahil Singla and Weinberg, {S. Matthew}",
note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 17th International Conference on Web and Internet Economics, WINE 2021 ; Conference date: 14-12-2021 Through 17-12-2021",
year = "2022",
doi = "10.1007/978-3-030-94676-0_16",
language = "English (US)",
isbn = "9783030946753",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "280--298",
editor = "Michal Feldman and Hu Fu and Inbal Talgam-Cohen",
booktitle = "Web and Internet Economics - 17th International Conference, WINE 2021, Proceedings",
address = "Germany",
}