Competitive Analysis of Two Special Online Device Replacement Problems

When anew investment opportunity of purchasing a new deviceoccurs, the investors must decide whether or not and when to buy this device in anonline fashion. That is, the online player must make an investment decision whileneither future demand for orders nor future investment opportunities are known. Thisproblem which generalizes the basic leasing problem has been introduced by Azar \itet al., and then two special cases have been studied by Damaschke. In the so-calledequal prices model a 2-competitive algorithm is devised and a 1.618 lowerbound is given. Here we make use of an averaging technique and obtain a better tightlower bound of 2, in other words, this lower bound cannot be improved.Furthermore, another special case which only considerstwo-stage device replacement is studied in this paper.Accounting for the interest rate is an essential featureof any reasonable financial model. Therefore, we explorethe two-stage model with and without the interest raterespectively. In addition, we introduce the risk-rewardmodel to analyze this problem and improve the competitive ratio performance.