离散型两斜率在线租赁问题

两斜率在线租赁问题是经典的在线租赁问题的一种自然的推广.基于在线租赁问题的研究分为离散时间和连续时间,鉴于已有文献对连续时间情况下两斜率在线租赁问题进行了讨论,本文研究离散时间情况下两斜率在线租赁问题.我们的讨论包括确定性竞争策略和随机性在线策略.关于确定性策略,一个竞争因数为2-1+(s-1)a]/s的最优策略被给出.对于随机性策略,本文提出了风险均衡策略,并通过竞争分析的方法证明了该策略是唯一最优策略.最后,对两种策略的竞争性能做了分析和讨论·分析和讨论的结果表明:考虑两斜率能改善经典问题的竞争比,考虑离散性能比连续性提高决策效率.

Discrete online leasing problem with two slopes

The two-slope online leasing problem is a natural generalization of the classic online leasing problem. Due to the fact that the two-slope online leasing problem of continuous-time has already been studied, we focus on the two-slope online leasing problem of discrete time in this study. Our discussion has taken the deterministic strategy and the randomized strategy into consideration. We demonstrated an optimal deterministic strategy, which could achieve competitive factor of 2-1+(s-1)a]/s. As for the randomized strategy, we proposed the strategy of risk balanced its absolute optimality through competitive analysis. Finally, analysis and discussions are carried out for the two types of strategies, mainly based on their competitive performances. It is found that, the two-slope analysis could improve the competitive ratio of the classic online leasing problems. In addition, by taking the discreteness into consideration rather than the continuity, the effectiveness of solving online leasing problem could be much improved.