Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 88 for “"Randomized algorithm"”.
-
An Online Algorithm for the 2-Server Problem On The Line with Improved Competitiveness
In this thesis we present a randomized online algorithm for the 2-server problem on the line, named R-LINE (for Randomized Line). This algorithm achieves the lowest competitive ratio of any known randomized algorithm for the 2-server problem on the line. The competitiveness of R-LINE is less than …
-
Efficient derandomization and simulation of BPP under assumptions
Randomized algorithms have proven extremely useful in both providing efficient solutions to computational problems, and extending our understanding of the limits of computation. But, in practice they have their downsides. First, the output of randomized algorithms is inherently uncertain. Second, …
-
An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem
… perform an experimental study of approximation algorithms for the tree augmentation problem (TAP). TAP is a fundamental problem in network design. The goal of TAP is to add the minimum number of edges from a given edge set to a tree so that it becomes 2-edge connected. Formally, given a tree T = …
-
Performance Comparison of Neighbor Discovery Protocols in Wireless Ad-Hoc Network
… to answer this question. We implemented one randomized and two deterministic algorithms for neighbor discovery and compared their performance in terms of number of rounds required as a function of the number of nodes in the network and the size of the space from which ids are chosen. Our …
-
Fast Algorithms for Finding the Characteristic Polynomial of a Rank-2 Drinfeld Module
This thesis introduces a new Monte Carlo randomized algorithm for computing the characteristic polynomial of a rank-2 Drinfeld module. We also introduce a deterministic algorithm that uses some ideas seen in Schoof's algorithm for counting points on elliptic curves over finite fields. Both …
-
COPIA: A New Software for Finding Consensus Patterns in Unaligned Protein Sequences
… more efficiently,a new scoring scheme and a randomized algorithm based on substitution matrix are proposed here. Any practical solutions to a bioinformatics problem must observe twoprinciples: (1) the problem that it solves accurately describes the real problem; in CPP, this requires the …
-
Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms
… studies the design and mathematical analysis of randomized approximation algorithms for the hitting set and b-matching problems in hypergraphs. We present a randomized algorithm for the hitting set problem based on linear programming. The analysis of the randomized algorithm rests upon the …
-
Path Centrality: A New Centrality Measure in Networks
… centrality. We present a polynomial-time randomized algorithm for distinguishing high k-path centrality vertices from low k-path centrality vertices in any given (unweighted or weighted) graph. Specifically, for any graph G = (V, E) with n vertices and for every choice of parameters α ∈ …
-
Big Data Algorithms with Limited Local Resources
… is huge, superlinear-time (e.g., quadratic-time) algorithms would be considered impractical. Therefore, we will study algorithms dealing with massive data that run in time nearly linear in N plus a polynomial of k and space polynomial in k. In particular, we will study algorithms that run in time …
-
Algorithms for finding orders and analyzing sets of chains
… show that it is NP-hard, and give an efficient randomized algorithm for finding approximate solutions to it. Moreover, we show that the expected cost of a solution found by the randomized algorithm differs from the optimal solution only by a constant factor. For the second approach we propose a …
-
Secure routing and data aggregation for infrastructureless wireless networks without persistent cryptographic operations
… data aggregation. For the first problem, a randomized algorithm is proposed to defend against malicious attackers wishing to disrupt routing in wireless ad-hoc networks. For the second problem, a solution is proposed to leverage the broadcast nature of wireless medium and use a special …
-
A few randomized protocols in peer-to-peer networks
This thesis studies a few randomized algorithms in application-layer peer-to-peer networks. The significant gain in scalability and resilience that peer-to-peer networks provide has made them widely used and adopted in many real-world distributed systems and applications. The unique properties of …
-
Non-crossing matching of online points
… is not allowed, we show that a simple greedy algorithm matches roughly 2n/3 points in the monochromatic case, which is the best that any deterministic algorithm can achieve in the worst-case scenario. For the bichromatic variant, we prove that for every deterministic algorithm Alg there is a …
-
Efficiently and effectively processing probabilistic queries on uncertain data
… skyline. Based on this model, an efficient exact algorithm and a randomized algorithm with & -approximation guarantee are developed for discrete and continuous cases, respectively. We extend skyline operator to streaming environment and study the problem of probabilistic skyline queries over …
-
Study of FPGA Implementation of Entropy Norm Computation for IP Data Streams
… purposes in IP data streams. Space efficient randomized algorithms for estimating entropy of data streams are available in the literature. However no hardware implementation of these algorithms is available. The main challenge to software implementation for IP data streams has been in storing …
-
On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures
… optimally as far as comparison-based algorithms are concerned, but there has been little work focusing on improving the constant factors hidden in big-Oh bounds on the number of comparisons needed. In this thesis, we consider orthogonal-type problems and present a number of results …
-
A Las Vegas Algorithm for the Ordered Majority Problem
… using ordered comparisons under the Las Vegas randomized algorithm model. The majority problem asks whether a given set of n elements, each with some colour, has a colour which appears on more than half of the elements. We focus on algorithms for this problem whose fundamental operation is to …
-
Distributed Energy Minimization in Heterogeneous Cellular Networks
… cellular networks. In this thesis, we present a randomized algorithm that addresses two challenges in HetNets, namely energy saving and throughput maximization, in a self-organizing manner. More specifically, the proposed algorithm seeks to maximize an objective function that balances the …
-
Reliable hierarchical matrix compression methods and their efficient parallelization for integral-equation based RCS prediction
… and simulation times. A novel iterative randomized algorithm for estimating the singular values of matrices arising from the discretization of physical kernels common in electromagnetics and acoustics is presented. The theoretical background supporting the algorithm’s efficacy is …
-
Strongly Linearizable LL/SC from CAS
… standard correctness condition for shared memory algorithms and is generally considered to be the practical equivalent of atomicity for deterministic algorithms. However, Golab, Higham, and Woelfel [16] showed that if we replace atomic objects used in a randomized algorithm with their linearizable …
Page 1 of 5