首页> 外文期刊>Algorithmica >Average-case competitive analyses for ski-rental problems
【24h】

Average-case competitive analyses for ski-rental problems

机译:滑雪租赁问题的平均案例竞争分析

获取原文
获取原文并翻译 | 示例

摘要

Let s be the ratio of the cost for purchasing skis over the cost for renting them. Then the famous result for the ski-rental problem shows that skiers should buy their skis after renting them (s - 1) times, which gives us an optimal competitive ratio of 2 - 1/s. In practice, however, it appears that many skiers buy their skis before this optimal point of time and also many skiers keep renting them forever. In this paper we show that this behavior of skiers is quite reasonable by using an average-case competitive ratio. For an exponential input distribution f (t) = lambda e-(lambda t,) optimal strategies are (i) if 1/lambda <= s, then skiers should rent their skis forever and (ii) otherwise they should purchase them after renting approximately s(2)lambda (< s) times. Thus average-case competitive analyses give us the result which differs from the worst-case competitive analysis and also differs from the traditional average cost analysis. Other distributions and related problems are also discussed.
机译:s为购买雪橇的成本与租用雪橇的成本之比。然后,关于滑雪租赁问题的著名结果表明,滑雪者应在租用(s-1)次后再购买滑雪板,这使我们的最佳竞争比为2-1 / s。然而,实际上,似乎有许多滑雪者在这个最佳时间点之前购买了他们的滑雪板,并且许多滑雪者一直在永久地租用它们。在本文中,我们通过使用平均情况下的竞争比率表明滑雪者的这种行为是相当合理的。对于指数输入分布f(t)= lambda e-(lambda t,),最佳策略是(i)如果1 / lambda <= s,则滑雪者应永久租用滑雪板;(ii)否则应在租用后购买滑雪板大约s(2)lambda(

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号