Known about the 2-server problem:
• For any metric space M, there is a 2-competitive online algorithm for the 2-server problem.
• If a metric space M has at least 3 points, there is no deterministic algorithm for the 2-server problem on M whose competitiveness is less than 2.
• For many classes of metric spaces, there are randomized online algorithms with competitiveness less than 2.
• There is no known randomized online algorithm with competitiveness less than 2 for all metric spaces. [15? years]
|