(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 Dates

December 11 – December 21: Fall Term Exam Period (includes tests and midterm exams for Fall/Winter Term classes)

December 22 – January 1: Winter Holiday (University Closed)

Upcoming Exams

MATH 1020 Final Exam
Monday, December 18 at 1:30 p.m.

MATH 2140 A01 Final Exam
Tuesday, December 19 at 9:00 a.m.

MATH 2160 A01 Final Exam
Wednesday, December 20 at 9:00 a.m.

MATH 3120 A01 Final Exam
Wednesday, December 20 at 9:00 a.m.

Upcoming Seminar

Colloquium talk:
Seth Wolbert
Friday, January 12 at 14:30, 418 Machray Hall.