Advance Notice: Talk by Dr. Jiri Sgall - Monday, October 2nd

[Margery Ishmael]

         Department of Computer Science/The University of Chicago

                    Ryerson Hall -- 1100 E. 58th Street

                 COLLOQUIUM   ANNOUNCEMENT

Dr. Jiri Sgall, Mathematical Institute, Academy of Sciences of the Czech 
Republic

Monday, 2 October at 2:30 in Ryerson 251
(To be followed by refreshments in Ryerson 255)

Title: On-line algorithms for weighted server problems

Abstract: Server problems provide a framework for studying on-line 
problems. In general, in a metric space, we are given a sequence of request 
points, and upon each request we have to move one of our servers to the 
given point. We measure the total distance travelled by the servers. In an 
on-line problem, we must make a decision for each request immediately,
without knowing the future requests. Such a solution is then compared to 
the best off-line solution which is obtained with advance knowledge of the 
request sequence.

In this talk we survey some basic and recent results in this area, with 
emphasis on the power of randomization and on various new variants of the 
problem that have been introduced and studied recently. These include file 
caching, the so called CNN problem, and the weighted server problem. We 
present some new results for the last problem with two servers with 
different costs; the distance traveled by each server is multiplied by its 
cost. In uniform spaces (i.e., all distances equal), we are able to give an 
optimal deterministic algorithm as well as the optimal memory-less 
randomized algorithm. For general metric spaces, we prove
that no memory-less randomized algorithm can achieve performance within a 
constant factor of the optimum and provide some partial results for the 
deterministic algorithms.

Host: Prof. Laszlo Babai

====================================================
Margery Ishmael
Department of Computer Science
1100 E. 58th St.
Chicago, IL 60637

tel: 773 834-8977  fax: 773 702-8487

marge at cs.uchicago.edu 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20000920/de9aee11/attachment.htm