| Title: | Online Algorithms and Competitive Analysis |
| Speaker: | Ben Coleman Graduate Student Computer Science College of William and Mary Williamsburg, VA |
| Abstract: | 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. |
| Location: | Norris 109 |
| Date: | 3/20/2003 |
| Time: | 4:10 PM |
@abstract{MCS:Colloquium:BenColeman
GraduateStudent
ComputerScience
CollegeofWilliamandMary
WilliamsburgVA:2003:3:20,
author = "{Ben Coleman
Graduate Student
Computer Science
College of William and Mary
Williamsburg, VA}",
title = "{Online Algorithms and Competitive Analysis}",
address = "{Albion College Mathematics and Computer Science Colloquium}",
month = "{20 March}",
year = "{2003}"
}