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"”.
-
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 …
-
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 …
-
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 …
-
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. …
-
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 …
-
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. …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
Online And Offline Facility Location And Network Design
… for these problems and their approximation ratio or competitive ratio analysis.
-
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 …
-
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 …
-
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, …
-
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 …
-
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 …
-
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 …
Page 1 of 4