Computer Science – Data Structures and Algorithms
Scientific paper
2008-06-05
Computer Science
Data Structures and Algorithms
Scientific paper
This paper provides a systematic study of several recently suggested measures for online algorithms in the context of a specific problem, namely, the two server problem on three colinear points. We examine how these measures evaluate the Greedy Algorithm and Lazy Double Coverage, commonly studied algorithms in the context of server problems. We examine Competitive Analysis, the Max/Max Ratio, the Random Order Ratio, Bijective Analyis and Relative Worst Order Analysis and determine how they compare the two algorithms. We find that by the Max/Max Ratio and Bijective Analysis, Greedy is the better algorithm. Under the other measures Lazy Double Coverage is better, though Relative Worst Order Analysis indicates that Greedy is sometimes better. Our results also provide the first example of an algorithm that is optimal under Relative Worst Order Analysis.
Boyar Joan
Irani Sandy
Larsen Kim S.
No associations
LandOfFree
A Comparison of Performance Measures for Online Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Comparison of Performance Measures for Online Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Comparison of Performance Measures for Online Algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-128184