Nearly optimal competitive online replacement policies

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 supplies 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 repalcement 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.