Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2006. / Includes bibliographical references (leaves [78]-84). Also available in electronic version.

Thesis (M. Phil.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.

Online computation is a model for formulating decision making under uncertainty. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step, the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as robot navigation are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the 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 online graph coloring. In this thesis, we first survey three classic online problems, namely the cow-path problem, the Processor-Allocation problem and the Robots-Search-Rays problem and highlight connections between them. Second, the main result is for the One-Robot-Searches-Two-Rays problem for which we consider the weighted scenario, in which the robot is located on a ray with a preferential probability p. We term the One-Robot-Searches-Two-Rays-And-Weighted problem as 1-STRAW (and in general k-STRAW for k searchers). In the 1-STRAW problem, we propose a search strategy which is optimal among weighted geometric states. In addition, we prove a tight lower bound of the worst case competitive ratio and conjecture a lower bound of the average case competitive ratio for the 1-STRAW problem. Additionally, we compare our search strategy and its performance with the doubling strategy and the SmartCow algorithm.

Online computation is a model for formulating decision making under uncertainty. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step, the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as robot navigation are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the 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 online graph coloring. In this thesis, we first survey three classic online problems, namely the cow-path problem, the Processor-Allocation problem and the Robots-Search-Rays problem and highlight connections between them. Second, the main result is for the One-Robot-Searches-Two-Rays problem for which we consider the weighted scenario, in which the robot is located on a ray with a preferential probability p. We term the One-Robot-Searches-Two-Rays-And-Weighted problem as 1-STRAW (and in general k-STRAW for k searchers). In the 1-STRAW problem, we propose a search strategy which is optimal among weighted geometric states. In addition, we prove a tight lower bound of the worst case competitive ratio and conjecture a lower bound of the average case competitive ratio for the 1-STRAW problem. Additionally, we compare our search strategy and its performance with the doubling strategy and the SmartCow algorithm.

We introduce two online models for the vertex k-center and the vertex k-median problems. Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges) are revealed sequentially, determining the topology of a graph over time. Clients are revealed by an adversary to an online algorithm that selects existing graph vertices on which to open facilities; once open, a facility cannot be removed or relocated. We define two models: an online algorithm may be restricted to open a facility only at the location of the most recent client or at the location of any existing client. We examine these models on three classes of graphs under two types of adversaries. We establish lower bounds on the respective competitive ratios attainable by any online algorithm for each combination of model, adversary, and graph class. Finally, we describe algorithms whose competitive ratios provide corresponding upper bounds on the best competitive ratios achievable.

We introduce two online models for the vertex k-center and the vertex k-median problems. Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges) are revealed sequentially, determining the topology of a graph over time. Clients are revealed by an adversary to an online algorithm that selects existing graph vertices on which to open facilities; once open, a facility cannot be removed or relocated. We define two models: an online algorithm may be restricted to open a facility only at the location of the most recent client or at the location of any existing client. We examine these models on three classes of graphs under two types of adversaries. We establish lower bounds on the respective competitive ratios attainable by any online algorithm for each combination of model, adversary, and graph class. Finally, we describe algorithms whose competitive ratios provide corresponding upper bounds on the best competitive ratios achievable.

Thesis (Ph.D.)--University of Melbourne, Dept. of Mechanical Engineering, School of Engineering, 2009. / Typescript. Includes bibliographical references (p. 177-184)

Thesis (M.S.)--Oregon State University, 2005. / Printout. Includes bibliographical references (leaves 106-108). Also available on the World Wide Web.

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

This thesis is concerned with caching algorithms. We investigate three variations of the caching problem: web caching in the Torng framework, relative competitiveness and caching with request reordering. <br /><br /> In the first variation we define different cost models involving page sizes and page costs. We also present the Torng cost framework introduced by Torng in [29]. Next we analyze the competitive ratio of online deterministic marking algorithms in the BIT cost model combined with the Torng framework. We show that given some specific restrictions on the set of possible request sequences, any marking algorithm is 2-competitive. <br /><br /> The second variation consists in using the relative competitiveness ratio on an access graph as a complexity measure. We use the concept of access graphs introduced by Borodin [11] to define our own concept of relative competitive ratio. We demonstrate results regarding the relative competitiveness of two cache eviction policies in both the basic and the Torng framework combined with the CLASSICAL cost model. <br /><br /> The third variation is caching with request reordering. Two reordering models are defined. We prove some important results about the value of a move and number of orderings, then demonstrate results about the approximation factor and competitive ratio of offline and online reordering schemes, respectively.