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 rat e. 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 swit ch activities so that his total cost is minimized. Typical application s 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 achievabl e 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.