Babaioff et al. [BIK2007] 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 \text{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.


翻译:Babaioff等人[BIK2007]在2007年引入了机器人秘书问题,这是典型的单选秘书问题自然延伸至机器人的延伸,并推测存在着一个持续竞争的在线算法。 尽管出现了实质性的部分进展,这种推测仍然没有定论,包括许多机器人特殊案例的不断竞争算法和一般案例中的美元(log\log\log\ text{rank})美元竞争算法。许多这些算法遵循了原则性框架。这些算法的局限性以前是未经研究的,而先前的工作仅确定少数特定的算法无法解决机器人秘书的推测。我们开始研究解决这一推测的框架不可能的结果。我们为自然的贪婪算法和随机分割算法确定了不可能的结果,这两种算法都包含解决特殊案例的已知算法。

0
下载
关闭预览

相关内容

CASES:International Conference on Compilers, Architectures, and Synthesis for Embedded Systems。 Explanation:嵌入式系统编译器、体系结构和综合国际会议。 Publisher:ACM。 SIT: http://dblp.uni-trier.de/db/conf/cases/index.html
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
50+阅读 · 2020年12月14日
已删除
德先生
53+阅读 · 2019年4月28日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
Arxiv
0+阅读 · 2022年1月11日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
已删除
德先生
53+阅读 · 2019年4月28日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
Top
微信扫码咨询专知VIP会员