
Prof. Dr. Guy Even
Max-Planck-Institut für Informatik
Saarland Informatics Campus
Campus E1 4 – Room 311A
66123 Saarbrückenmore
Saarland Informatics Campus
Campus E1 4 – Room 311A
66123 Saarbrückenmore
Departments
ALGO
Many computational decisions must be made before the entire input is known. We study online algorithms, which process requests as they arrive without knowing future requests. A central question is how closely their performance can approach that of an optimal algorithm with advance knowledge of the complete input. We develop algorithms with provable competitive guarantees and investigate lower bounds that capture the inherent cost of uncertainty. Our goal is to understand the possibilities and limitations of making efficient decisions with incomplete information.




