A fast approximate implementation of the work function algorithm for solving the k-server problem (CROSBI ID 224287)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Rudec, Tomislav ; Manger, Robert
engleski
A fast approximate implementation of the work function algorithm for solving the k-server problem
In this paper we propose an approximate implementation of the work function algorithm (WFA) for solving the k-server problem. Our implementation is based on network flow techniques, a novel network model, and flow cost reduction. Also, it is provided with a parameter that enables tradeoff between accuracy and speed. In the paper we present experiments, showing that the new implementation can mimic perfectly the original WFA and still run at least an order of magnitude faster than any known exact implementation.
combinatorial optimization ; on-line computation ; k-server problem ; work function algorithm ; implementation ; network flows ; cost reduction
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
23 (3)
2015.
699-722
objavljeno
1435-246X
1613-9178
10.1007/s10100-014-0349-4
Povezanost rada
Matematika, Računarstvo