多类秘书问题的最优算法设计及竞争比分析

After the introduction of secretary problem in 1960', there are a lot of research work about this problem which is one of the most important problems in optimal stopping theory. People pay much attention on the generalizations of secretary problem, like K-best secretary problem, matroid secretary problem, or submodular secretary problem, etc. And they design many different strategies of such problems and analyze the corresponding competitive ratios..This project plans to study the optimal strategy of different secretary problems.We propose observation-selection based framework of the strategy design for secretary problems. This method takes advantage of the relationship between linear programming description and strategy of secretary problem so as to obtain the optimal strategy. We will start with the deterministic optimal strategy for K-best J-selection secretary problem. We then extend our framework into matroid secretary problem and submodular secretary problem in order to analyze the property of their optimal strategies. Last, we will compute the competitive ratios of the strategies we proposed and analyze their properties..The main contribution of this project is not only the collection of a few optimal strategies, but also the general method and tool which can be used in several kinds of secretary problems. We hope this method can also inspire research work in optimal stopping theory, online algorithm or other fields.

自19世纪60年代秘书问题被提出之后,该问题作为最优停止理论中的一个重要问题就受到了广泛的关注。K-最优、拟阵、子模等多类秘书问题都有很多研究工作，研究这些问题的最优策略是什么，所能达到的最优竞争比又是什么。.本项目计划对多类秘书问题的最优策略以及其所对应的最优竞争比进行研究。我们提出基于观察-选择思想的算法设计框架，巧妙利用其与线性规划刻画之间的联系,证明所得到的算法是问题的最优策略。我们计划从K-最优J-选择秘书问题的最优确定性算法出发，将其设计思想推广到拟阵和子模模型中，考察其最优策略的结构性质，进而设计最优算法。在这个过程中，不断完善本项目所提出的理论方法和工具。.本项目不仅是设计几个具体问题的最优策略，而是侧重于提出系统性、通用性的理论方法和工具，能够应用于多类秘书问题，并希望所提出的方法能从理论上对观察-选择的直观思想给出解释。

自19世纪60年代秘书问题被提出之后,该问题作为最优停止理论中的一个重要问题就受到了广泛的关注。K-最优、拟阵、子模等多类秘书问题都有很多研究工作，研究这些问题的最优策略是什么，所能达到的最优竞争比又是什么。.在本项目中，我们对多类秘书问题的最优策略以及其所对应的最优竞争比进行了算法设计与竞争比的分析研究，把K-最优J-选择秘书问题的最优确定性算法进一步推广到了有多个队列、或者有决策窗口等等更一般的情况。之后，项目进一步把秘书问题的设计思想推广到了其他优化问题的在线算法设计上，如在线二部图匹配问题、基于动态数据的排序问题、影响力传播问题等等，均得到了很好的理论分析结果。对在线二部图匹配问题，还成功的应用到了广告投放的实际应用场景中，得到了很好的实验效果。