Delayed information and action in on-line algorithms

Susanne Albers, Moses Charikar, Michael Mitzenmacher

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations


Most on-line analysis assumes that, at each time-step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time relevant information is available and the time a decision has an effect may be decoupled. For example, when making an investment, one might not have completely up-to-date information on market prices. Similarly, a buy or sell order might only be executed some time later in the future. We introduce and explore natural delayed models 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.

Original languageEnglish
Pages (from-to)71-80
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 39th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: 8 Nov 199811 Nov 1998


Dive into the research topics of 'Delayed information and action in on-line algorithms'. Together they form a unique fingerprint.

Cite this