Master of Science in Computer Science
First Committee Member
Lawrence L. Larmore
Second Committee Member
Third Committee Member
Number of Pages
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 theory, and linear programming.
Client/server computing – Equipment and supplies; Competitive analysis; k-server problem; Online algorithms
Computer Sciences | Digital Communications and Networking | OS and Networks
Bang, Lucas Adam, "An Online Algorithm for the 2-Server Problem On The Line with Improved Competitiveness" (2013). UNLV Theses, Dissertations, Professional Papers, and Capstones. 1801.