loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
39th Annual Symposium on Foundations of Computer Science
Delayed Information and Action in On-line Algorithms
Palo Alto, California
November 08-November 11
ISBN: 0-8186-9172-7
Susanne Albers, Max-Planck-Institut fur Informatik
Moses Charikar, Stanford University
Michael Mitzenmacher, Compaq Systems Research Center
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.
Index Terms:
Online Algorithms, Delay, Load Balancing, Stock Trading
Citation:
Susanne Albers, Moses Charikar, Michael Mitzenmacher, "Delayed Information and Action in On-line Algorithms," focs, pp.71, 39th Annual Symposium on Foundations of Computer Science, 1998
Usage of this product signifies your acceptance of the Terms of Use.