Managing Multiple Mobile Resources

We extend the Mobile Server problem introduced in Feldkord and Meyer auf der Heide (TOPC 6(3), 14:1-14:17 2019) to a model where k identical mobile resources, here named servers, answer requests appearing at points in the Euclidean space. To reduce communication costs, the positions of the servers can be adapted by a limited distance m(s) per round for each server. The costs are measured similarly to the classical Page Migration problem: i.e., answering a request induces costs proportional to the distance to the nearest server, and moving a server induces costs proportional to the distance multiplied with a weight D. We show that, in our model, no online algorithm can have a constant competitive ratio: i.e., one which is independent of the input length n, even if an augmented moving distance of (1 + delta)m(s) is allowed for the online algorithm. Therefore we investigate a restriction of the power of the adversary dictating the sequence of requests: We demand locality of requests: i.e., that consecutive requests come from points in the Euclidean space with distance bounded by some constant m(c). We show constant lower bounds on the competitiveness in this setting (independent of n, but dependent on k, m(s) and m(c)). On the positive side, we present a deterministic online algorithm with bounded competitiveness when an augmented moving distance and locality of requests is assumed. Our algorithm simulates any given algorithm for the classical k-Page Migration problem as guidance for its servers and extends it by a greedy move of one server in every round. The resulting competitive ratio is polynomial in the number of servers k, the ratio between m(c) and m(s), the inverse of the augmentation factor 1/delta and the competitive ratio of the simulated k-Page Migration algorithm. We also show how to directly adapt the Double Coverage algorithm (Chrobak et al. SIAM J. Discrete Math. 4(2), 172-181 11) for the k-Server problem to receive an algorithm with improved competitiveness on the line.

Automated summary

In this model of Mobile Server problem, online algorithms cannot achieve a constant competitive ratio with an augmented moving distance, but can have bounded competitiveness with assumptions of augmented moving distance and locality of requests. The study also presents a deterministic online algorithm with bounded competitiveness and demonstrates how to adapt the Double Coverage algorithm for the k-Server problem with improved competitiveness.