Weighted Cache Location Problem with Identical Servers

This paper extends the well-known -CLP with one server to -CLP with identical servers, denoted by -CLP. We propose the closest server orienting protocol (CSOP), under which every client connects to the closest server to itself via a shortest route on given network. We abbreviate -CLP under CSOP to -CSOP CLP and investigate that -CSOP CLP on a general network is equivalent to that on a forest and further to multiple CLPs on trees. The case of is the focus of this paper. We first devise an improved -time parallel exact algorithm for -CLP on a tree and then present a parallel exact algorithm with at most time in the worst case for -CSOP CLP on a general network. Furthermore, we extend the idea of parallel algorithm to the cases of to obtain a worst-case -time exact algorithm. At the end of the paper, we first give an example to illustrate our algorithms and then make a series of numerical experiments to compare the running times of our algorithms.