Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Engineering
An Online Algorithm For The 2-Server Problem On The Line With Improved Competitiveness, Lucas Adam Bang
An Online Algorithm For The 2-Server Problem On The Line With Improved Competitiveness, Lucas Adam Bang
UNLV Theses, Dissertations, Professional Papers, and Capstones
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 (approximately 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 …