Competitive k-Server Algorithms (Extended Abstract)

Deterministic competitive k-server algorithms are given for all k and all metric spaces. This settles the k-server conjecture of M. S. Manasse et al. (1988) up to the competitive ratio. The best previous result for general metric spaces was a three-server randomized competitive algorithm and a nonconstructive proof that a deterministic three-server competitive algorithm exists. The competitive ratio the present authors can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open. The methods set forth here also give competitive algorithms for a natural generalization of the k-server problem, called the k-taxicab problem. >

Authors

• Amos Fiat
• Yuval Rabani
• Yiftach Ravid

Keywords

• Extraterrestrial measurements
• Costs
• Upper bound
• Computer science
• Mathematics
• Current measurement
• Space exploration
• Competitive Algorithm
• Competitive Ratio
• Active Region
• Optimization Algorithm
• Path Length
• Maximum Distance
• Additional Term
• Pair Of Points
• Set Of Algorithms
• Current Events
• Complete Phase
• Optimal Cost
• Ratio Of Cases
• Version Of Problem
• Online Algorithm
• Cost Of Algorithm
• Sum Of Radii
• Concentric Spheres