Events Calendar

CS Colloq: Niv Buchbinder - CANCELLED

Talk Title: Randomized k-Server Conjecture (Online Algorithms meet Linear Programming)
Speaker: Dr. Niv Buchbinder
Host: Prof. David KempeTALK CANCELLEDAbstract:
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.Bio:
Niv Buchbinder is a post-doctoral researcher at Microsoft Research, New England at Cambridge, MA.
Previously, he was a Ph.D. student in Computer Science at Technion, Israel Institute of Technology under the supervision of Prof Seffi Naor.
His main research interests are algorithms for combinatorial problems in offline and online settings. He is also interested in algorithmic game theory problems.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Front Desk