An Optimal On-Line Algorithm for K Servers on Trees

1 February 1991

journal article
Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing

Vol. 20 (1), 144-148
https://doi.org/10.1137/0220008

Abstract

The k-server problem is investigated when the metric space is a tree. For this case an on-line k-competitive algorithm for k-servers is presented. The competitiveness ratio k is optimal. The algorithm is memoryless, in the sense that it does not use any information from the past.

Keywords

68Q20
ON-LINE ALGORITHMS
THE SERVER PROBLEM
COMPETITIVE ANALYSIS
METRIC SPACES
TREES

This publication has 4 references indexed in Scilit:

A competitive 2-server algorithm
Information Processing Letters, 1991
A strongly competitive randomized paging algorithm
Algorithmica, 1991
Memory versus randomization in on-line algorithms
Published by Springer Science and Business Media LLC ,1989
Competitive snoopy caching
Algorithmica, 1988

Cited by 114 articles