[Colloquium] TTIC Talk: Niv Buchbinder, Microsoft Research New England

[Julia MacGlashan]

*REMINDER*

When:             *Wednesday, Jan 27 @ 11:00am*

Where:           * TTIC Conference Room #526*, 6045 S Kenwood Ave


Who:              * **Niv Buchbinder*, Microsoft Research New England


Title:          *      **The Randomized k-Server Conjecture (Online
Algorithms meet Linear Programming)*



 The k-server problem is one of the most central and well studied problems
in competitive analysis and is considered by many to be the "holy grail"
problem in the field. In the k-server problem, there is a distance function
d defined over an n-point metric space and k servers located at the points
of the metric space. At each time step, an online algorithm is given a
request at one of the points of the metric space, and it is served by moving
a server to the requested point. The goal of an online algorithm is to
minimize the total sum of the distances traveled by the servers so as to
serve a given sequence of requests. The k-server problem captures many
online scenarios, and in particular the widely studied paging problem.

A twenty year old conjecture states that there exists a k-competitive online
algorithm for any metric space. The randomized k-server conjecture states
that there exists a randomized O(log k)-competitive algorithm for any metric
space.

While major progress was made in the past 20 years on the deterministic
conjecture, only little is known about the randomized conjecture.

We present a very promising primal-dual approach for the design and analysis
of online algorithms. We survey recent progress towards settling the
k-server conjecture achieved using this new framework.

Host:              Yury Makarychev, yury at ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100126/332f8fc1/attachment.htm