A new approach to solve the k-server problem based on network flows and flow cost reduction (CROSBI ID 189594)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Rudec, Tomislav ; Manger, Robert
engleski
A new approach to solve the k-server problem based on network flows and flow cost reduction
This paper is concerned with two algorithms for solving the k-server problem: the optimal off-line algorithm (OPT) and the on-line work function algorithm (WFA). Both algorithms are usually implemented by network flow techniques including the flow augmentation method. In the paper a new implementation approach is proposed, which is again based on network flows, but uses simpler networks and the cost reduction method. The paper describes in detail the corresponding new implementations of OPT and WFA, respectively. All necessary correctness proofs are given. Also, experiments are presented, which confirm that the new approach assures faster execution of both algorithms.
on-line problems; k-server problem; optimal off-line algorithm; work function algorithm; implementation; network flows; cost reduction; experiments
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
40 (4)
2013.
1004-1013
objavljeno
0305-0548
10.1016/j.cor.2012.11.006