关键词: k-秘书搜索问题')">在线k-秘书搜索问题, 秘书问题, \lambda-竞争率')">\lambda-竞争率, 竞争比, 竞争差

Abstract:

In this study， the onlinek-secretary search problem is studied basing on the\lambda-competitive rate criterion （where，\lambdais the preference）. Firstly， a threshold-type online strategyOK{S}_{\lambda }is designed basing on a nonlinear programmingNL{P}_{\lambda }with variables\left\{{\phi }_{\lambda ,\mathrm{1}}^{\mathrm{*}},{\phi }_{\lambda ,\mathrm{2}}^{\mathrm{*}},\cdots ,{\phi }_{\lambda ,k}^{\mathrm{*}},{\gamma }_{\lambda }^{\mathrm{*}}\right\}. The steps of solving for the thresholds {\phi }_{\lambda ,\mathrm{1}}^{\mathrm{*}},{\phi }_{\lambda ,\mathrm{2}}^{\mathrm{*}},\cdots ,{\phi }_{\lambda ,k}^{\mathrm{*}}are given and it is further proved thatm\le {\phi }_{\lambda ,\mathrm{1}}^{\mathrm{*}}\le {\phi }_{\lambda ,\mathrm{2}}^{\mathrm{*}}\le \cdots \le {\phi }_{\lambda ,k}^{\mathrm{*}}\le M. The strategyOK{S}_{\lambda }is proved to be optimal in the sense of the\lambda-competitive rate and its\lambda-competitive rate is{\gamma }_{\lambda }^{\mathrm{*}}.In the special case analyses when\lambda =\mathrm{1}and\lambda =\mathrm{0}， it is found that when\lambda =\mathrm{1}the competitive rate is just the competitive ratio， which is consistent with the results of Lorenz et al.； when\lambda =\mathrm{0}the competitive rate is just the competitive difference， where the explicit expression of{\gamma }_{\lambda }^{\mathrm{*}}can be obtained. It is further proved that the threshold{\phi }_{\mathrm{0},i}^{\mathrm{*}}which is based on competitive difference is larger than the threshold{\phi }_{\mathrm{1},i}^{\mathrm{*}}which is based on the competitive ratio， implying that the online strategy based on the competitive ratio is more conservative. In the special case analyses whenk=\mathrm{1}， the onlinek-secretary search problem degenerates into the the classical online time series search problem proposed by El-Yaniv et al. and optimal online strategies based on competitive ratio and competitive difference are both presented， respectively.Finally， numerical simulation experiments reveal that： （1） the larger the preference\lambdathe smaller the threshold{\phi }_{\lambda ,i}^{\mathrm{*}}， i.e.， the larger the preference\lambdathe more conservative the strategy is， and vice versa the more aggressive it is； （2） When the expectation of a candidate's rating sequence is small， an online strategy with a large preference should be selected； when the expectation of the rating sequence is moderate， an online strategy with a moderate preference should be selected； when the expectation of the rating sequence is large， an online strategy with a small preference should be selected.

Key words: k-search problem')">onlinek-search problem, secretary problem, \lambda-competitive rate')">\lambda-competitive rate, competitive ratio, competitive difference