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.