Award Date

5-1-2013

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Lawrence L. Larmore

Second Committee Member

Wolfgang Bein

Third Committee Member

Ebrahim Salehi

Number of Pages

56

Abstract

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.

Keywords

Client/server computing – Equipment and supplies; Competitive analysis; k-server problem; Online algorithms

Disciplines

Computer Sciences | Digital Communications and Networking | OS and Networks

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS