Delayed information and action in on-line algorithms

Most on-line analysis assumes that, at each time step, all relevant informa tion up to that time step is available and a decision has an immediate effe ct. In many on-line problems, however, the time when relevant information i s available and the time a decision has an effect may be decoupled. For exa mple, when making an investment, one might not have completely up-to-date i nformation on market prices. Similarly, a buy or sell order might only be e xecuted some time in the future. We introduce and explore natural delayed m odels for several well-known on-line problems. Our analyses demonstrate the importance of considering timeliness in determining the competitive ratio of an on-line algorithm. For many problems, we demonstrate that there exist algorithms with small competitive ratios even when large delays affect the timeliness of information and the effect of decisions. (C) 2001 Academic P ress.