The Taub Faculty of Computer Science Events and Talks

Uncertainty is a key factor in real-time systems, where decisions must be made over time based on incomplete or partial information. Competitive analysis is the prominent paradigm for the design and analysis of algorithms for such environments, which are called online algorithms. The field of competitive analysis has been studied extensively throughout the last few decades, and is highly useful in the analysis of such real-time systems. In an online problem data is revealed over time and, from time to time, a decision must be made. Naturally, a decision at time $t$ can be based only on data that was revealed up until time $t$ (and on previous online decisions), without knowledge of future occurrences. The performance of an online algorithm is measured in term of competitive ratio, i.e., how its performance compares to the solution of an optimal algorithm that has complete information about the input in advance. We study two families of online problems - aggregation problems, and caching problems. We present several algorithmic results for problems that fall into at least one of these two families.