Advertisement
Published in:
01-05-2015
The online \(k\)-server problem with max-distance objective
Published in: Journal of Combinatorial Optimization | Issue 4/2015
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
This paper studies the online \(k\)-server problem with max-distance objective, i.e. minimizing the maximum distance moved among all the servers. For this objective, we prove that no deterministic online algorithm has a competitive ratio better than \(k\). We also analyze several classical algorithms for two special cases and show that some algorithms do have a competitive ratio of \(k\) and hence optimal. Consequently, we conjecture that any metric space allows for a deterministic \(k\)-competitive \(k\)-server algorithm with max-distance objective.