Naslov
A fast work function algorithm for solving the k-server problem

Autori
Rudec, Tomislav ; Baumgartner, Alfonzo ; Manger, Robert

Izvornik
Central European Journal of Operations Research (1435-246X) 21 (2013), 1; 187-205

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
on-line problems; on-line algorithms; k-server problem; work function algorithm; implementation. network flows

Sažetak
This paper deals with the work function algorithm (WFA) for solving the on-line k-server problem. The paper addresses some practical aspects of the WFA, such as its efficient implementation and its true quality of serving. First, an implementation of the WFA is proposed, which is based on network flows, and which reduces each step of the WFA to only one minimal-cost maximal flow problem instance. Next, it is explained how the proposed implementation can further be simplified if the involved metric space is finite. Also, it is described how actual computing of optimal flows can be speeded up by taking into account special properties of the involved networks. Some experiments based on the proposed implementation and improvements are presented, where actual serving costs of the WFA have been measured on very large problem instances and compared with costs of other algorithms. Finally, suitability of the WFA for solving real-life problems is discussed.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA