Albion College Mathematics and Computer Science Colloquium

 Title: Online Algorithms and Competitive Analysis Speaker: Ben ColemanGraduate StudentComputer ScienceCollege of William and MaryWilliamsburg, 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:BenColemanGraduateStudentComputerScienceCollegeofWilliamandMaryWilliamsburgVA:2003:3:20,
author  = "{Ben ColemanGraduate StudentComputer ScienceCollege of William and MaryWilliamsburg, VA}",
title   = "{Online Algorithms and Competitive Analysis}",
address = "{Albion College Mathematics and Computer Science Colloquium}",
month   = "{20 March}",
year    = "{2003}"
}