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"”.

  1. 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 …

    unlv Repository record for An Online Algorithm for the 2-Server Problem On The Line with Improved Competitiveness (opens in a new tab) Download PDF for An Online Algorithm for the 2-Server Problem On The Line with Improved Competitiveness (opens in a new tab)

  2. 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, …

    texas Repository record for Efficient derandomization and simulation of BPP under assumptions (opens in a new tab)

  3. 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 = …

    wvu Repository record for An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem (opens in a new tab)

  4. 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 …

    tamu Repository record for Performance Comparison of Neighbor Discovery Protocols in Wireless Ad-Hoc Network (opens in a new tab)

  5. 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 …

    waterloo Repository record for Fast Algorithms for Finding the Characteristic Polynomial of a Rank-2 Drinfeld Module (opens in a new tab)

  6. 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 …

    waterloo Repository record for COPIA: A New Software for Finding Consensus Patterns in Unaligned Protein Sequences (opens in a new tab)

  7. 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 …

    cau-kiel Repository record for Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms (opens in a new tab)

  8. 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 α ∈ …

    usf Repository record for Path Centrality: A New Centrality Measure in Networks (opens in a new tab)

  9. 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 …

    tamu Repository record for Big Data Algorithms with Limited Local Resources (opens in a new tab)

  10. 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 …

    aalto Repository record for Algorithms for finding orders and analyzing sets of chains (opens in a new tab)

  11. 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 …

    uvic Repository record for Secure routing and data aggregation for infrastructureless wireless networks without persistent cryptographic operations (opens in a new tab)

  12. 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 …

    uoit Repository record for A few randomized protocols in peer-to-peer networks (opens in a new tab)

  13. 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 …

    manitoba Repository record for Non-crossing matching of online points (opens in a new tab)

  14. 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 …

    unsw Repository record for Efficiently and effectively processing probabilistic queries on uncertain data (opens in a new tab)

  15. 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 …

    usf Repository record for Study of FPGA Implementation of Entropy Norm Computation for IP Data Streams (opens in a new tab)

  16. 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 …

    waterloo Repository record for On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures (opens in a new tab)

  17. 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 …

    waterloo Repository record for A Las Vegas Algorithm for the Ordered Majority Problem (opens in a new tab)

  18. 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 …

    calgary Repository record for Distributed Energy Minimization in Heterogeneous Cellular Networks (opens in a new tab)

  19. 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 …

    texas Repository record for Reliable hierarchical matrix compression methods and their efficient parallelization for integral-equation based RCS prediction (opens in a new tab)

  20. 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 …

    calgary Repository record for Strongly Linearizable LL/SC from CAS (opens in a new tab)

Page 1 of 5