Home / research areas / OA
Online Algorithms
In an online problem, the instance is a sequence of pieces, and each of these piece must be processed without any knowledge of those that are still to come. For each part, the algorithm makes irrevocable decisions that affect its solution. Therefore, online algorithms are the right tools to handle problems under incomplete information. Several real-world problems have online features. This is the case in many scenarios where the quality of a decision depends on a set of events that may or may not happen. One example occurs in the stock exchange, where the quality of the decision on which stocks to buy can only be fully evaluated when selling the stocks. In another example, the decision of acquiring a new industrial equipment depends on the future demand variation.
Online algorithms form a multidisciplinary field which is the interest of Economics, Operational Research and Computer Science. In Computer Science, the studied online problems can be divided into several classes and arise in many contexts. For example, we have online versions of classical optimization problems, such as the Packaging, Scaling and Load Balancing problems. Some typical online problems are the List Access problem, the Virtual Memory Paging problem and its generalization, the k-Server problem.
Problems:
- Packing;
- Scheduling;
- Load Balancing;
- List update;
- Paging;
- k-Center.
References:
- Borodin e El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Amazon
- Amos Fiat e Gerhard J. Woeginger. Online Algorithms: The State of the Art (Lecture Notes in Computer Science). Springer, 1998. Amazon
- Susanne Albers. Online algorithms. In Interactive Computation: The New Paradigm edited by D.Q. Goldin, S.A. Smolka and P. Wegner, 143-164, 2006. Chapter is available in author’s page.
- Reza Dorrigiv e Alejandro Lopez-Ortiz. A Survey of Performance Measures for On-line Algorithms. ACM SIGACT (Special Interest Group on Automata and Computability Theory) News, 36 (3): 67-81, 2005. ACM
- Buchbinder e Naor. The Design of Competitive Online Algorithms via a Primal-Dual Approach. Now Publishers Inc, 2009. Amazon