An online algorithm for the 2-server problem on the line with improved competitiveness.

摘要

In this thesis we present a randomized online algorithm for the 2-server problem on the line, named R-LINE (for Randomized Line). This algorithm achieves the lowest competitive ratio of any known randomized algorithm for the 2-server problem on the line. The competitiveness of R-LINE is less than 1.901. This result provides a significant improvement over the previous known competitiveness of 155/78 ≈ 1.987, by Bartal, Chrobak, and Larmore, which was the first randomized algorithm for the 2-server problem one the line with competitiveness less than 2. Taking inspiration from this algorithm,we improve this result by utilizing ideas from T-theory, game theory, and linear programming.