Albion College
Mathematics and Computer Science
COLLOQUIUM
Online Algorithms and Competitive Analysis
Ben Coleman
Graduate Student
Computer Science
College of William and Mary
Williamsburg, VA
In online computation, an algorithm must decide how to handle incoming requests without knowledge of future requests. The quality of these algorithms is not evaluated as correct or incorrect, but instead is measured relative to the performance of an algorithm that has complete knowledge of the future. This technique, called competitive analysis, has been applied to numerous problems in Computer Science. In this talk, I will formally define online computation and introduce the study of online algorithms though competitive analysis. I will give representative examples of online algorithms and present the proof of the competitive ratio for a simple online scheduling algorithm.
4:10 PM
All are welcome!
Norris 109
March 20, 2003