Award Date

1-1-2007

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Lawrence L. Larmore

Number of Pages

105

Abstract

Several advancements in Online Algorithms can be credited to T-theory, a field of discrete mathematics. T-theory has aided in the development of several online algorithms for the k-server problem, although the standard notation of T-theory was not used at the time of their creation; A summary of the k-server problem, and some important concepts of T-theory, are given. A number of known k-server results are restated using the established terminology of T-theory. Included is a 3-competitiveness proof, using T-theory, for the HARMONIC algorithm for two servers, which was presented in a paper by Larmore and Oravec [71]; Previously, the Knowledge State Method was documented in Kurlinski's thesis [70]. Additional research and analysis was done by Larmore and Oravec. Summaries of that work, as well as prior work by Larmore and Bein are given; Research supported by NSF grain CCR-0312093.

Keywords

Algorithms; Analysis; Online Theory

Controlled Subject

Computer science

File Format

pdf

File Size

2099.2 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

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

Download


COinS