T-Theory Applications to Online Algorithms for the Server Problem

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Although largely unnoticed by the online algorithms community, T-theory, a field of discrete mathematics, has contributed to the development of several online algorithms for the k-server problem. A brief summary of the k-server problem, and some important application concepts of T-theory, are given. Additionally, a number of known k-server results are restated using the established terminology of T-theory. Lastly, a previously unpublished 3-competitiveness proof, using T-theory, for the Harmonic algorithm for two servers is presented.
19 figures 38 pages

Keywords

Data Structures and Algorithms, Discrete Mathematics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/118859

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0611088
 http://arxiv.org/abs/cs/0611088

Collections

arXiv