This paper discusses the odds problem, proposed by Bruss in 2000, and its variants. A recurrence relation called a dynamic programming (DP) equation is used to find an optimal stopping policy of the odds problem and its variants. In 2013, Buchbinder, Jain, and Singh proposed a linear programming (LP) formulation for finding an optimal stopping policy of the classical secretary problem, which is a special case of the odds problem. The proposed linear programming problem, which maximizes the probability of a win, differs from the DP equations known for long time periods. This paper shows that an ordinary DP equation is a modification of the dual problem of linear programming including the LP formulation proposed by Buchbinder, Jain, and Singh.
翻译：本文件讨论了布鲁斯在2000年提出的胜算问题及其变式。一个称为动态方案(DP)等式的重现关系被用来寻找对胜算问题及其变式的最佳制止政策。 2013年,Buchbinder、Jain和Singh提出了线性方案(LP)拟订办法,以寻找对古典秘书问题的最佳制止政策,这是胜算问题的一个特例。拟议的线性方案拟定问题(这是赢率最大化的概率)与长期以来已知的DP等式不同。本文表明,普通的DP等式是对线性方案拟订的双重问题的修改,包括Buchbinder、Jain和Singh提议的LP拟订办法。
相关内容
微信扫码咨询专知VIP会员