A Polylogarithmic-Competitive Algorithm for the k-Server Problem

We give the first polylogarithmic-competitive randomized algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log 3 n log 2 k) for any metric space on n points. This improves upon the (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou (J. ACM 1995) whenever n is sub-exponential in k.

Authors

• Nikhil Bansal 0001
• Niv Buchbinder
• Aleksander Madry
• Joseph Naor

Keywords

• Resource management
• Servers
• Algorithm design and analysis
• Extraterrestrial measurements
• Vectors
• Probability distribution
• Algorithm For Problem
• K-server Problem
• Competitive Algorithm
• Competitive Ratio
• Deterministic
• Time Step
• Optimum Solution
• Description Of Algorithm
• Problem Instances
• Maximum Norm
• Cost Of Solution
• Online Algorithm
• Integral Solution
• Fractional Problem
• Fractional Solution
• Cost Of Movement
• Polylogarithmic
• randomized algorithms
• competitive analysis