Competitive Analysis of Two Special Online Device Replacement Problems  

作　　者：辛春林 马卫民 杨磊 

机构地区：[1]School of Economics and Management,Tsinghua University,Beijing 100084,China [2]School of Economics and Management,Tongji University,Shanghai 200092,China

出　　处：《Journal of Computer Science & Technology》2008年第2期203-213,共11页计算机科学技术学报（英文版）

基　　金：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);the Foundation for the Author of National Excellent Doctoral Dissertation of China(Grant No.200782).

摘　　要：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.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.

关 键 词：online algorithm device replacement competitive analysis competitive ratio 

分 类 号：TP274[自动化与计算机技术—检测技术与自动化装置]