The k-server problem deals with the dynamic allocation of a limited number of servers to process requests in real-time, aiming to optimize server movements to reduce the overall traveled distance. This computational challenge explores strategies for efficiently adapting to dynamic demands, making decisions without knowledge of future requests. The goal is to develop algorithms that strike a balance between responsiveness and optimality when presented with unpredictable sequences of requests. Algorithm performance is evaluated through competitive ratios between online algorithms and an optimal static algorithm. In this thesis, I implemented (in Python) the most well-known algorithms for solving the k-server problem and assessed their effectiveness. The Fast Work Function algorithm proved to be the most successful.
|
