El-Yaniv, Ran; Karp, Richard M. Nearly optimal competitive online replacement policies. (English) Zbl 0894.68076 Math. Oper. Res. 22, No. 4, 814-839 (1997). Summary: This paper studies the online replacement problem. In this problem, an online player is engaged at each time in one activity. Associated with each activity are a changeover cost and flow rate. While involved in an activity the player’s budget is depleted at the activity’s flow rate. The player can switch to a new activity whenever it is offered but he pays a changeover cost. The player’s goal is to decide when to switch activities so that his total cost is minimized. Typical applications are: equipment, jobs and supplier replacement, mortgage refinancing, etc. With respect to the competitive ratio performance measure, this paper seeks to determine the best possible competitive ratio achievable by an online replacement policy. Our results include the following: a general lower bound on the performance of any deterministic policy, a policy that is optimal in several special cases and a simple policy that is approximately optimal. Cited in 8 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 90B25 Reliability, availability, maintenance, inspection in operations research 91A05 2-person games Keywords:online replacement problem; competitive ratio PDFBibTeX XMLCite \textit{R. El-Yaniv} and \textit{R. M. Karp}, Math. Oper. Res. 22, No. 4, 814--839 (1997; Zbl 0894.68076) Full Text: DOI Link