This repository includes a somewhat naive approach to the Work Function Algorithm for finite general psuedo metric spaces in Python. The implementation is based on the dynamic programming algorithm given in "The k-server problem"-Koutsoupias which is a summary paper which includes the algorithm that Koutsoupias and Papadimitriou introduced earlier.
wfa.py - the class implementation
wfa_example.py - an example of the algorithm running on a Euclidean grid with the usual metric. Running will produce PNGs in a figs/ folder.
make_mpg.sh - generates a MOV file from the figures. Requires ImageMagick and the ffmpeg plugin.
Given k servers on a pseudometric space, determine a sequence of configurations in an online manner so that a given sequence of requests is served by a server in each corresponding configuration.
The algorithm has been proven to be (2k-1)-competitive on general metric spaces and has been conjectured to be k-competitive. In a practical sense, this means that no matter how poor a choice requests are, the cost of the Work Function Algorithm is guaranteed to perform no worse than (2k-1) times worse than an optimal algorithm that knows all requests ahead of time. It is known that no deterministic online algorithm can do better than k times the optimal offline.
The Work Function Algorithm balances the greedy algorithm (assigning the closest server to a request) and the retrospective algorithm (moves servers the optimal configuration assuming the current request is the terminating request). It is the best proven competitive algorithm known for the k-server problem. There are flow implementations that are polynomial in k and the number of points in the space, however this is the original exponential time algorithm with a number of amoritisations included.
There will be two main updates in the coming months,
-
Fast implementation based on "A fast implementation of the optimal offline algorithm for solving the k-server problem"- Rudec et al.
-
Limited memory implementation based on "Work function algorithm can forget history without losing competitiveness"- Colussi
Both of these will make using the algorithm more practical or even just feasible for large spaces, sequence lengths and numbers of servers.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent