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 6 of 6 for “"list update"”.

  1. Alternative Approaches for Analysis of Bin Packing and List Update Problems

    … for the analysis of online bin packing and list update problems. These are two classic online problems which are extensively studied in the literature and have many applications in the real world. Similar to other online problems, the framework of competitive analysis is often used to study …

    waterloo Repository record for Alternative Approaches for Analysis of Bin Packing and List Update Problems (opens in a new tab)

  2. Higher Compression from the Burrows-Wheeler Transform with New Algorithms for the List Update Problem

    … are some of the many algorithms used on the List Update problem. In 1985, Competitive Analysis first showed the superiority of Move-To-Front over Transpose and Frequency Count for the List Update problem with arbitrary data. Earlier studies due to Bitner assumed independent identically …

    unt Repository record for Higher Compression from the Burrows-Wheeler Transform with New Algorithms for the List Update Problem (opens in a new tab)

  3. Alternative Measures for the Analysis of Online Algorithms

    … results, for certain problems it results in unrealistically pessimistic ratios and/or fails to distinguish between algorithms that have vastly differing performance under any practical characterization. Addressing these shortcomings has been the subject of intense research by many of the best …

    waterloo Repository record for Alternative Measures for the Analysis of Online Algorithms (opens in a new tab)

  4. New Analytical Methods for Online Binary Search Trees

    … counting, a popular potential function for list updates that has not been used in a BST context. An inversion potential function is arguably the most natural potential function, as it captures the difference between the states of two different algorithms. We illustrate our techniques in the …

    aalto Repository record for New Analytical Methods for Online Binary Search Trees (opens in a new tab)