Memoryless Algorithms for the Generalized k-server Problem on Uniform Metrics
share
We consider the generalized k-server problem on uniform metrics. We study the power of memoryless algorithms and show tight bounds of Θ(k!) on their competitive ratio. In particular we show that the Harmonic Algorithm achieves this competitive ratio and provide matching lower bounds. This improves the ≈ 2^2^k doubly-exponential bound of Chiplunkar and Vishwanathan for the more general setting of uniform metrics with different weights.
READ FULL TEXT