[Colloquium] Today: Turkoglu/MS Presentation/Nov. 7, 2005

[Margaret Jaffey]

This is a reminder about Duru Turkoglu's Master's Presentation this  
afternoon.

------------------------------
Date:  Monday, November 7, 2005

Time:  1:30 p.m.

Place:  Ryerson 255

M.S. Candidate:  Duru Turkoglu

M.S. Paper Title:  The k-Server Problem and Fractional Analysis

Abstract:
The k-server problem, introduced by Manasse, McGeoch and Sleator
is a fundamental online problem where k mobile servers are required
to serve a sequence of requests on a metric space, with the minimum
possible movement cost. Despite the conjectured existence of a
\Theta(log k)-competitive randomized algorithm, the best known upper
bound for arbitrary metric spaces is 2k-1. Even for one of the
simplest cases, the Euclidean metric on the interval [0,1], nothing
better than k is known. In this work, we first give a survey of the
k-server problem, and then introduce a fractional version in order to
provide a different perspective on randomized algorithms for this
problem. In this version, servers can move fractionally instead of
moving as a unit, and in the process, servicing a request requires
providing one unit server at the point of request. We show that on
the line and circle, the randomized version of the problem is
equivalent to the fractional version. We also classify the cases for
which these versions are not equivalent by presenting a fractional
algorithm which cannot be simulated by any randomized algorithm.
Furthermore, we investigate and analyze some algorithms on the line
using the fractional setting.

Advisors:  Professors Adam Kalai and Laszlo Babai

A draft copy of Duru Turkoglu's MS Paper is available in Ry 161A.


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey                             margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)        (773) 702-6011
The University of Chicago                  http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=