2010 Sep 08 at 11:00
DC 2314
Ying (Catherine) Liu , graduate student, David R. Cheriton School of Computer Science, Univ. of waterloo
Competitive analysis is a standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to onine graph coloring. In this thesis, we first study three classic online problems, namely the Cow-Path problem, the Processor-Allocation problem and the Robot-Search-Ray problem and highlight connections between them. Second, the main result is for the One-Robot-Two-Rays problem for which we consider the weighted scenario, in which the robot locates on a ray with preferential probability p, which we term as 1-STRAW (and in general k-STRAW for k searchers). We propose a search strategy which is optimal among weighted geometric states. Additionally, we prove a tight lower bound of the worst case competitive ratio and conjecture a lower bound of the average case competitive ratio for 1-STRAW.