T-Theory Applications to Online Algorithms for the Server Problem
<|reference_start|>T-Theory Applications to Online Algorithms for the Server Problem: 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.<|reference_end|>
@article{larmore2006t-theory,
    title={T-Theory Applications to Online Algorithms for the Server Problem},
    author={Lawrence L. Larmore and James A. Oravec},
    journal={arXiv preprint arXiv:cs/0611088},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0611088},
    primaryClass={cs.DS cs.DM}
}