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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Randomized Algorithm for Online k-Server Problem on a Line

  • Mohammad Shamim Ahsan,
  • Abu Reyan Ahmed,
  • Md. Saidur Rahman

摘要

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.