(Department of Computer Science, University of Manitoba)

k-server problems: a review of the old results and recent developments

Date: Friday, December 1, 2017

k-server problem is a classic problem in the context of competitive analysis. Given an undirected graph and a sequence of requests to vertices of the graph, the goal is to move k servers in way that at least one server is present at each request and the total distance moved by servers is minimized. At the heart of the k-server problem lies the k-server conjecture, which states that there is a deterministic algorithm with competitive ratio of exactly k. In the first half of this talk, we review the existing results with respect to the k-server conjecture. This will include a lower bound for competitive ratio of deterministic algorithms, particular case of trees, and also the work-function algorithm which is conjectured to answer the k-server conjecture in the affirmative. In the past few years, there has been efforts to study k-server problem using alternative settings. One of them is advice model where the online constraint is relaxed and an online algorithm receives partial information about the input sequence. In the second part of the talk, we review the existing results on the advice complexity of the k-server problem. We conclude with discussing a few open problems.

Click for abstract

Important Date

April 9 – April 23: Winter Term Exam Period (includes final exams for Fall/Winter Term classes)