On Two Special Cases of Online Device Replacement Problem
Chunlin Xin, Weimin Ma, Lei Yang · 2007
When a new investment opportunity of purchasing a new device occurs, the investor must decide whether or not and when to buy this device in an online fashion. This problem which generalizes the basic leasing problem has been introduced by Y.Azar et al, and then two special cases have been studied by P.Damaschke. In the so-called equal prices model a 2-competitive algorithms 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, that is, this lower bound can not be improved. Furthermore, another special case which considers two-stage device replacement is studied in this paper. We introduce the risk-reward model to analyze this problem and improve the competitive ratio.