东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

Competitive analysis of two special online device replacement problems

ISSN号：1000-9000
期刊名称：计算机科学技术学报(英文版)
时间：0
页码：203-213
语言：中文
分类：TP393[自动化与计算机技术—计算机应用技术;自动化与计算机技术—计算机科学与技术]
作者机构：[1]School of Economics and Management, Tsinghua University, Beijing 100084, China, [2]School of Economics and Management, Tongji University, Shanghai 200092, China
相关基金：This work is supported by China Postdoctoral Science Foundation （Grant No. 20070420029）, the National Science Foundation of China （Grant Nos. 70671004, 70401006, and 70521001）, the Beijing Natural Science Foundation Program （Grant No. 9073018） for New Century Excellent Talents in Universities （Grant No. NCET-06-0172） and the Foundation for the Author of National Excellent Doctoral Dissertation of China （Grant No. 200782）.
相关项目：局内不确定性决策理论及其在运输管理中的应用研究

作者： Ma, Wei-Min|Xin, Chun-Lin|Yang, Lei|

关键词：在线装置还原系统, 计算机, 网络系统, 分析方法, online algorithm, device replacement, competitive analysis, competitive ratio

中文摘要：

当购买一台新设备的一个新投资机会发生时，投资者必须决定是否并且什么时候以一种联机方式买这台设备。当对订单也不未来投资机会的任何一个未来要求都不被知道时，也就是说，联机播放器必须做一个投资决定。概括基本租借问题的这个问题被 Azar 等引入了，然后二种特殊情况被 Damaschke 学习了。在价格建模的所谓的平等者，一个 2-competitive 算法被设计， 1.618 下界被给。这里，我们使用一种平均技术并且换句话说，获得 2 的更好紧密的下界这下界不能被改进。而且，仅仅考虑二阶段的设备代替的另一种特殊情况在这篇论文被学习。为利率的财务是任何合理财务模型的一个必要特征。因此，我们分别地有或没有利率探索二阶段的模型。另外，我们介绍风险报酬模型分析这个问题并且改进竞争比率表演。电子增补材料这篇文章(doi:10.1007/s11390-008-9122-2 ) 的联机版本包含增补材料，它对授权用户可得到。

英文摘要：

When a new investment opportunity of purchasing a new device occurs, the investors must decide whether or not and when to buy this device in an online fashion. That is, the online player must make an investment decision while neither future demand for orders nor future investment opportunities are known. This problem which generalizes the basic leasing problem has been introduced by Azar et al., and then two special cases have been studied by Damaschke. In the so-called equal prices model a 2-competitive algorithm is devised and a 1.618 lower bound is given. Here we make use of an averaging technique and obtain a better tight lower bound of 2, in other words, this lower bound cannot be improved. Furthermore, another special case which only considers two-stage device replacement is studied in this paper. Accounting for the interest rate is an essential feature of any reasonable financial model. Therefore, we explore the two-stage model with and without the interest rate respectively. In addition, we introduce the risk-reward model to analyze this problem and improve the competitive ratio performance.

同期刊论文项目