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

项目编号: 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

成为VIP会员查看完整内容
0

相关内容

【AI+军事】附论文+PPT 《重新评估隐藏者-引导者问题》
专知会员服务
45+阅读 · 2022年4月16日
【干货书】算法设计艺术,319页pdf
专知会员服务
113+阅读 · 2021年10月24日
算法分析导论, 593页pdf
专知会员服务
144+阅读 · 2021年8月30日
专知会员服务
121+阅读 · 2021年8月25日
【2021新书】分布式优化,博弈和学习算法,227页pdf
专知会员服务
217+阅读 · 2021年5月25日
最新《非凸优化理论》进展书册,79页pdf
专知会员服务
105+阅读 · 2020年12月18日
【NeurIPS 2020 Tutorial】离线强化学习:从算法到挑战,80页ppt
【经典书】C++编程:从问题分析到程序设计,1491页pdf
专知会员服务
58+阅读 · 2020年8月11日
专知会员服务
41+阅读 · 2020年7月29日
领域驱动编程,代码怎么写?
阿里技术
0+阅读 · 2022年3月15日
做了一年企业内部系统,我学会了竞争和博弈
人人都是产品经理
0+阅读 · 2022年3月14日
过度设计会扼杀你的产品
InfoQ
0+阅读 · 2022年3月5日
你听的随机播放音乐,可能是算法下的伪随机
人人都是产品经理
0+阅读 · 2022年2月20日
工作几年了,还没成为“算法人上人”?
PaperWeekly
1+阅读 · 2022年1月14日
我,产品半年,加班3周,连个需求分析都做不好......
人人都是产品经理
1+阅读 · 2021年11月6日
经典书《复杂性思考》,158页pdf
专知
3+阅读 · 2021年5月8日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
4+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
24+阅读 · 2021年6月25日
Arxiv
12+阅读 · 2021年5月3日
Arxiv
11+阅读 · 2018年5月13日
小贴士
相关VIP内容
【AI+军事】附论文+PPT 《重新评估隐藏者-引导者问题》
专知会员服务
45+阅读 · 2022年4月16日
【干货书】算法设计艺术,319页pdf
专知会员服务
113+阅读 · 2021年10月24日
算法分析导论, 593页pdf
专知会员服务
144+阅读 · 2021年8月30日
专知会员服务
121+阅读 · 2021年8月25日
【2021新书】分布式优化,博弈和学习算法,227页pdf
专知会员服务
217+阅读 · 2021年5月25日
最新《非凸优化理论》进展书册,79页pdf
专知会员服务
105+阅读 · 2020年12月18日
【NeurIPS 2020 Tutorial】离线强化学习:从算法到挑战,80页ppt
【经典书】C++编程:从问题分析到程序设计,1491页pdf
专知会员服务
58+阅读 · 2020年8月11日
专知会员服务
41+阅读 · 2020年7月29日
相关资讯
领域驱动编程,代码怎么写?
阿里技术
0+阅读 · 2022年3月15日
做了一年企业内部系统,我学会了竞争和博弈
人人都是产品经理
0+阅读 · 2022年3月14日
过度设计会扼杀你的产品
InfoQ
0+阅读 · 2022年3月5日
你听的随机播放音乐,可能是算法下的伪随机
人人都是产品经理
0+阅读 · 2022年2月20日
工作几年了,还没成为“算法人上人”?
PaperWeekly
1+阅读 · 2022年1月14日
我,产品半年,加班3周,连个需求分析都做不好......
人人都是产品经理
1+阅读 · 2021年11月6日
经典书《复杂性思考》,158页pdf
专知
3+阅读 · 2021年5月8日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
4+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
微信扫码咨询专知VIP会员