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...
详细信息
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. (C) 2012 Elsevier Ltd. All rights reserved.
暂无评论