Delayed information and action in on-line algorithms

Citation
S. Albers et al., Delayed information and action in on-line algorithms, INF COMPUT, 170(2), 2001, pp. 135-152
Citations number
36
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION AND COMPUTATION
ISSN journal
08905401 → ACNP
Volume
170
Issue
2
Year of publication
2001
Pages
135 - 152
Database
ISI
SICI code
0890-5401(20011101)170:2<135:DIAAIO>2.0.ZU;2-N
Abstract
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.