CATS Seminar
Capital Area Theory Seminar
http://www.umiacs.umd.edu/users/liberato/cats/
Computational Clairvoyance
Bala Kalyanasundaram
University of Pittsburgh
Friday, November 12, 1999, TBA p.m.
TBA
Special day/time
Abstract
Competitive analysis has been widely used to measure the performance of an online algorithm. Ideally, a (small) constant competitive online algorithm A is considered to be good since its performance is comparable to that of a clairvoyant offline optimal algorithm. In other words, we say that A has computational clairvoyance. There are numerous problems for which no online algorithm has computational clairvoyance. This leads to a question: What does it take to gain computational clairvoyance? In this talk I will answer this question in a positive way for many practical problems from scheduling, real-time scheduling, fault-tolerant scheduling, web-broadcasting and web-caching.
Contact: Bill Gasarch.
The Capital Area Theory Symposia is an NSF sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department and UMIACS. NSF support under grant CCR-9732907 is gratefully acknowledged.