Award Date
1-1-1999
Degree Type
Thesis
Degree Name
Master of Science (MS)
Department
Computer Science
First Committee Member
Wolfgang W. Bein
Number of Pages
56
Abstract
The online 2-server problem presents a number of challenges in the search for simple competitive algorithms for solving it. Finding the optimal off-line solution involves costly dynamic programming. Looking for more efficient algorithms, researchers have studied how restriction on the input information given to the algorithm affects its competitiveness. One such restriction is tracklessness. Trackless algorithms for the 2-server problem include many known server algorithms including BALANCE_SLACK and some paging algorithms. It is demonstrated that the trackless 2-server optimization problem has a deterministic lower bound of 2311>2 for competitiveness, thus proving that tracklessness is a significant restriction. The optimally competitive online non-trackless algorithm for the 2-server problem is 2-competitive. Other current research on the topic is also discussed.
Keywords
Black; Games; Online; Problems; Red; Server; Trackless; Two
Controlled Subject
Computer science
File Format
File Size
1341.44 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.
Repository Citation
Naydenova, Anna N, "Trackless online two-server problems and red-black games" (1999). UNLV Retrospective Theses & Dissertations. 1065.
http://dx.doi.org/10.25669/3u4f-oikm
Rights
IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/
