Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, piano secondo
Aula C2

Abstract:
We consider the general on-line two server problem in which at each step both servers receive a request, which is a point in a metric space. One of the servers has to be moved to its request. The special case where the requests are points on the real line is known as the CNN-problem. It has been a well-known open question if an algorithm with a constant competitive ratio exists for this problem. We answer this question in the affirmative sense by providing an algorithm that is 23808-competitive on any metric space. The constant is huge and the algorithm is rather ugly but our main goal was indeed to settle the question. We believe that our result gives new insight in the problem and will lead to more and much better algorithms for the general $k$-server problem in the near future.

Joint work with Leen Stougie and Willem de Paepe.