A k-server problem with parallel requests and unit distances

• We consider k-server problems with parallel requests.
• The surplus-situation and the scarcity-situation are distinguished.
• We show that the Harmonic algorithm is competitive in the case of unit distances.
• For this we use the method of the potential function by Bartal/Grove.

In this paper we consider k-server problems with parallel requests where several servers can also be located on one point. We will distinguish the surplus-situation where the request can be completely fulfilled by means of the k servers and the scarcity-situation where the request cannot be completely met. We use the method of the potential function by Bartal and Grove [2] in order to prove that a corresponding Harmonic algorithm is competitive for the more general k-server problem in the case of unit distances. For this purpose we partition the set of points in relation to the online and offline serversʼ positions and then use detailed considerations related to sets of certain partitions.