Spelling suggestions: "subject:"anline algorithms"" "subject:"0nline algorithms""
1 |
Online exploration and search in graphs /Trippen, Gerhard Wolfgang. January 2006 (has links)
Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2006. / Includes bibliographical references (leaves [78]-84). Also available in electronic version.
|
2 |
Improved analysis of flow time schedulingLiu, Kin-shing. January 2005 (has links)
Thesis (M. Phil.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.
|
3 |
Geometric On-line Ray Searching Under Probability of Placement ScenariosLiu, Ying January 2010 (has links)
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.
|
4 |
Geometric On-line Ray Searching Under Probability of Placement ScenariosLiu, Ying January 2010 (has links)
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.
|
5 |
Online problems in facility locationMehrabidavoodabadi, Saeed 22 August 2012 (has links)
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.
|
6 |
Online problems in facility locationMehrabidavoodabadi, Saeed 22 August 2012 (has links)
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.
|
7 |
On-line scheduling with constraints /Zhang, Lele. January 2009 (has links)
Thesis (Ph.D.)--University of Melbourne, Dept. of Mechanical Engineering, School of Engineering, 2009. / Typescript. Includes bibliographical references (p. 177-184)
|
8 |
Design of on-line arithmetic networks for signal processing applications : a color filter implementation /Sinky, Mohammed H. January 1900 (has links)
Thesis (M.S.)--Oregon State University, 2005. / Printout. Includes bibliographical references (leaves 106-108). Also available on the World Wide Web.
|
9 |
Improved analysis of flow time schedulingLiu, Kin-shing., 廖建誠. January 2005 (has links)
published_or_final_version / abstract / Computer Science / Master / Master of Philosophy
|
10 |
Variations on the Theme of CachingGaspar, Cristian January 2005 (has links)
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.
|
Page generated in 0.0467 seconds