Randomized Algorithm for Online k-Server Problem on a Line
摘要
In the k-server problem, the server units are depicted as locations within a metric space, and a series of requests arise in real time within that environment. A server must fulfill a request by moving to the location where it is situated before the next request is introduced. The aim is to minimize the total movements of the server units. In this study, we present a new randomized approach for the k-server problem on a line. We show that this approach achieves a \(\frac{99}{100}k\) competitive ratio against any adaptive online adversary, which enhances the competitive ratio of the current deterministic method for \(1 < k < 99\) , where \(N=2k+1\) points are evenly distributed along a line. We assign a Boolean variable to each server to improve the performance of the algorithm and also demonstrate the necessity of this Boolean variable at the end of the paper.