Seminars

View all Seminars  |  Download ICal for this event

The Weighted k-server Problem: How well can we compete?

Series: Bangalore Theory Seminars

Speaker: Ashish Chiplunkar.Indian Institute of Technoloby Delhi

Date/Time: Mar 22 11:00:00

Location: Microsoft team - online talk

Abstract:
The k-server problem is a cornerstone problem in online computation in which requests at points in a metric space are to be served by k mobile servers while minimizing the server movement. The weighted k-server problem is a natural generalization of the k-server problem in which the cost incurred in moving a server is the distance traveled times the weight of the server. Even after almost three decades since the seminal work of Fiat and Ricklin (1994) on the weighted k-server problem, the competitive ratio of this problem remains poorly understood. Even on the simplest class of metric spaces -- the uniform metric spaces, the best known upper bound on the randomized competitive ratio is doubly exponential in k, while, until recently, the best known lower bound was only logarithmic in k. In this talk, I will present a significant step towards understanding the randomized competitive ratio of weighted k-server on uniform metrics: a lower bound that is exponential in k. If time permits, I will discuss the best known randomized algorithm that is actually memoryless in the sense that it moves servers according to a fixed probability distribution independent of the history. <br />
<br />
The talk is based on joint works with Nikhil Ayyadevara and Sundar Vishwanathan.<br />
<br />
Microsoft teams link:<br /><br />
Link /><br />
<br /><br />
We are grateful to the Kirani family for generously supporting the theory seminar series<br /><br />

Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Manisha Padala