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

项目名称： 多类秘书问题的最优算法设计及竞争比分析

项目编号： No.61502449

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 自动化技术、计算机技术

项目作者： 张家琳

作者单位： 中国科学院计算技术研究所

项目金额： 20万元

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

中文关键词： 秘书问题；在线算法；最优确定性算法；竞争比；线性规划

英文摘要： 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.

英文关键词： secretary problem;online algorithm;optimal deterministic algorithm;competitive ratio;linear programming