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 79 for “"Competitive ratio"”.

  1. A New Competitive Ratio for Network Applications with Hard Performance Guarantee

    … need to make decisions without future knowledge. Competitive ratio is used to evaluate the performance of an online algorithm. This ratio is the worst-case ratio between the performance of the online algorithm and the offline optimal algorithm. However, the competitive ratios in many current …

    tamu Repository record for A New Competitive Ratio for Network Applications with Hard Performance Guarantee (opens in a new tab)

  2. Online square packing with prediction

    … to design algorithms that balance consistency (competitive ratio with accurate predictions) and robustness (competitive ratio under adversarial prediction errors), acknowledging the impact of prediction error on algorithm efficiency. This novel approach, diverging from traditional models with …

    manitoba Repository record for Online square packing with prediction (opens in a new tab)

  3. Applications and extensions of the bin packing problem

    … approximation factor (in offline setting), and competitive ratio (in online setting). In the "square packing problem", items are squares of various side lengths, and bins are unit squares. We study this problem in both offline and online settings. Unlike previous work, we allow an algorithm to …

    manitoba Repository record for Applications and extensions of the bin packing problem (opens in a new tab)

  4. On-Line Algorithms and the k-Server Conjecture

    … for the ^-server problem, is shown to have competitive ratio at most 2k —1 for all metric spaces. It is also shown that the ^-server conjecture, which states that there is an on-line algorithm for the /^-server problem with competitive ratio k, holds for all metric spaces with k + 2 points. …

    greece Repository record for On-Line Algorithms and the k-Server Conjecture (opens in a new tab)

  5. Variations on the Theme of Caching

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

    waterloo Repository record for Variations on the Theme of Caching (opens in a new tab)

  6. Online algorithms for dynamic aggregation problems

    … of the online algorithm is measured by the competitive ratio which is the worst-case ratio between the online cost and the optimal offline cost. We consider the online variants of the Min-Sum Set Cover problem, the K-Facility Reallocation problem and the Dynamic Facility Location problem. …

    greece Repository record for Online algorithms for dynamic aggregation problems (opens in a new tab)

  7. Computational Geometry and Online Algorithms

    … algorithms can have arbitrarily bad competitive ratios due to adversarial weight assignments. To address this, we consider weights within the range [1, U] and provide an algorithm with a competitive ratio of Omega (2^{-2 sqrt{ log U }}), along with an upper bound of O(2^{-sqrt{log …

    concordia Download PDF for Computational Geometry and Online Algorithms (opens in a new tab)

  8. Supporting Software Transactional Memory in Distributed Systems: Protocols for Cache-Coherence, Conflict Resolution and Replication

    … the performance of D-STM by measuring the competitive ratio of its makespan --- i.e., the ratio of its makespan (the last completion time for a given set of transactions) to the makespan of an optimal off-line clairvoyant scheduler. We show that the performance of D-STM for metric-space …

    vt Repository record for Supporting Software Transactional Memory in Distributed Systems: Protocols for Cache-Coherence, Conflict Resolution and Replication (opens in a new tab)

  9. Online scheduling algorithms for average flow time and its variants

    … measure for online scheduling algorithms is competitive ratio. An algorithm is said to be $c$-competitive if its objective is within a multiplicative factor $c$ of the optimal scheduler's objective for any sequence of requests. Roughly speaking, an algorithm with a small competitive ratio …

    uiuc Repository record for Online scheduling algorithms for average flow time and its variants (opens in a new tab)

  10. Analysis of algorithms for online routing and scheduling in networks

    … the efficiency of an online algorithm by its competitive ratio, which is the maximum ratio, over all request sequences, of the cost of the online algorithm's solution to that of an optimal solution constructed by knowing all the requests in advance.;We identify and study two distinct …

    wm-mary Repository record for Analysis of algorithms for online routing and scheduling in networks (opens in a new tab)

  11. Online Delivery and Dispatch with Capacity Constraints

    … specifically path graphs, which enable precise competitive analysis under capacity limitations. We distinguish between myopic algorithms, which dispatch requests immediately, and far-sighted algorithms, which delay service to batch future requests. For path graphs with unit capacity, we analyze …

    buffalo Repository record for Online Delivery and Dispatch with Capacity Constraints (opens in a new tab)

  12. Online Steiner Cover Problems in Hypergraphs

    … of an online algorithm is measured by the competitive ratio, which is the ratio between the cost of a solution obtained by the online algorithm to that of an optimal offline solution. Besides some simpler preliminary results, we obtain a lower bound on the competitive ratio for \treePN …

    concordia Download PDF for Online Steiner Cover Problems in Hypergraphs (opens in a new tab)

  13. Competitive cache replacement strategies for a shared cache

    … sequences. We establish tight bounds on the competitive ratio of deterministic and randomized cache replacement strategies when processes share memory blocks. Our main result for this case is a deterministic algorithm called GLOBAL-MAXIMA which is optimum up to a constant factor when …

    texas Repository record for Competitive cache replacement strategies for a shared cache (opens in a new tab)

  14. Online And Offline Facility Location And Network Design

    … for these problems and their approximation ratio or competitive ratio analysis.

    cornell Repository record for Online And Offline Facility Location And Network Design (opens in a new tab)

  15. Online algorithms for content caching: an economic perspective

    … content, is an effective way to optimize the operations of computer networks. Therefore, content caching reduces the delivery delay and improves the users’ Quality of Experience (QoE). The current literature either proposes offline algorithms that have complete knowledge of the request profile a …

    njit Repository record for Online algorithms for content caching: an economic perspective (opens in a new tab)

  16. Online t-interval scheduling

    … extent. The performance of the algorithm is the ratio between the number of tintervals in its output vs. the optimal offline schedule. If the intervals are weighted, the performance is the ratio between the total weight of these sets. The maximum ratio, taken over all input instances, is the …

    reykjavik Repository record for Online t-interval scheduling (opens in a new tab)

  17. Geometric On-line Ray Searching Under Probability of Placement Scenarios

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

    waterloo Repository record for Geometric On-line Ray Searching Under Probability of Placement Scenarios (opens in a new tab)

  18. Algorithms for Allocation Problems in Online Settings

    … computational challenge that arises in the operation of online systems, services, and platforms is that of resource allocation. Broadly defined, a resource allocation problem is one where set of users generate demands, which then have to be satisfied using a limited set of resources. In many of …

    duke Repository record for Algorithms for Allocation Problems in Online Settings (opens in a new tab)

  19. Some combinational optimization problems on radio network communication and machine scheduling

    … shown that Hu 's algorithm yields an asymptotic competitive ratio of 3/2 for intree precedence constraints and an asymptotic competitive ratio of 1 for outtree precedences, and Coffinan-Graham algorithm yields an asymptotic competitive ratio of 1 for arbitrary precedence constraints and two …

    njit Repository record for Some combinational optimization problems on radio network communication and machine scheduling (opens in a new tab)

  20. ON-LINE NETWORK SCHEDULING IN EMERGENCY OPERATION FOR MEDICAL RESOURCES WITH SINGLE-PROCESSOR SINGLE-DESTINATION

    … for such an on-line algorithm is the so-called competitive ratio. This thesis considers four cases of such a problem: (1) the capacity of vehicles for transporting medical resources and the number of vehicles are both in nite, (2) the capacity of vehicles is in nite but the number of vehicles is …

    sask Repository record for ON-LINE NETWORK SCHEDULING IN EMERGENCY OPERATION FOR MEDICAL RESOURCES WITH SINGLE-PROCESSOR SINGLE-DESTINATION (opens in a new tab)

Page 1 of 4