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 3 of 3 for “"Work Function Algorithm"”.

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

    The Work Function Algorithm, a natural algorithm 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 …

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

  2. Combinatorial Algorithms for Server Allocation Problem

    … velocity is also given as input. We present new algorithms for the Euclidean bipartite matching problem, showing improvements over existing algorithms. In particular, for two point sets $A, B subset mathbb{R}^d$ with $|A| = |B| = n$ and dimension $d > 1$ being constant, we developed: …

    vt Repository record for Combinatorial Algorithms for Server Allocation Problem (opens in a new tab)

  3. Empirical Analysis of Algorithms for the k-Server and Online Bipartite Matching Problems

    … we present an empirical analysis of a new online algorithm for k-server problem. This algorithm maintains two solutions, online solution, and an approximately optimal offline solution. When a request arrives we update the offline solution and use this update to inform the online assignment. This …

    vt Repository record for Empirical Analysis of Algorithms for the k-Server and Online Bipartite Matching Problems (opens in a new tab)