R–LINE: A better randomized 2-server algorithm on the line

A randomized on-line algorithm is given for the 2-server problem on the line, with competitiveness less than 1. 901 against the oblivious adversary. This improves the previously best known competitiveness of 155 78 ≈ 1. 987 for the problem. The algorithm uses a new approach and defines a potential in terms of isolation indices from T-theory.

Authors

• Lucas Bang
• Wolfgang Bein
• Lawrence L. Larmore

Keywords

• Online algorithms
• Randomized algorithms
• Server problem
• Algorithm design
• T-theory
• Game theory