论文标题
将简单算法扩展到Matroid秘书问题
Extension of Simple Algorithms to the Matroid Secretary Problem
论文作者
论文摘要
尽管有一些简单的算法被证明是对经典和多项选择秘书问题的最佳选择，但矩阵秘书问题尚不清楚。本文提出了来自经典和多项选择版本的一些简单算法在Matroid秘书问题上的概括。在两种基于样品做出决定的算法中，例如Dynkin的算法，一种被证明是贪婪算法的实例（Bahrani等，2022），而另一个则不是。虚拟算法的广义版（Babaioff等，2018）获得了帽子图的持续竞争比，这是贪婪算法的对手示例，但是当将略微修改引入该图时，但未能这样做。我们表明，在所有图形矩阵上，没有具有强大的禁止集（Soto等，2021）的算法。
Whereas there are simple algorithms that are proven to be optimal for the Classical and the Multiple Choice Secretary Problem, the Matroid Secretary Problem is less thoroughly understood. This paper proposes the generalization of some simple algorithms from the Classical and Multiple Choice versions on the Matroid Secretary Problem. Out of two algorithms that make decisions based on samples, like the Dynkin's algorithm, one is proven to be an instance of Greedy Algorithm (Bahrani et al., 2022), while the other is not. A generalized version of the Virtual Algorithm (Babaioff et al., 2018) obtains a constant competitive ratio for the Hat Graph, the adversarial example for Greedy Algorithms, but fails to do so when a slight modificiation is introduced to the graph. We show that there is no algorithm with Strong Forbidden Sets (Soto et al., 2021) of size 1 on all graphic matroids.
