Supervisor

Suitable for

Abstract

Description: The k-server problem is a fundamental problem in the field of online algorithms: There are k mobile “servers” located in a metric space. One by one, requests appear at points of the space, and each request must be served immediately by moving a server to the requested point, without knowledge of future requests. The goal is to minimize the distance moved by servers. The k-server conjecture — arguably the most famous open problem in online algorithms — asserts that there exists an algorithm whose distance traveled is at most k times the optimum in hindsight, on any instance. An algorithm conjectured to achieve this has been known for over 30 years, but no one has been able to prove it. On specific small metric spaces, it is possible to test the validity of the conjecture with an exhaustive computer search. Similar computer searches recently refuted some stronger conjectures that would have implied the k-server conjecture. In light of these results, and the very recent refutation of the sibling “randomized k-server conjecture”, some specific metric spaces suggest themselves as potential counter-examples. In this project, the student will implement and run a search for counter-examples on some relevant metric spaces, and determine whether they satisfy the conjecture or not.