Weighted cache location problem with identical servers

This paper extends the well-known p-clp with one server to p-clp with m ≥ 2 identical servers,denoted by (p,m)-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 (p,m)-clp under csop to (p,m)-csop clp and investigate that (p,m)-csop clp on a general network is equivalent to that on a forest and further to multiple clps on trees. the case of m = 2 is the focus of this paper. we first devise an improved o (ph2+n)-time parallel exact algorithm for p-clp on a tree and then present a parallel exact algorithm with at most o((4/9)p2n2) time in the worst case for (p,2)-csop clp on a general network. furthermore,we extend the idea of parallel algorithm to the cases of m > 2 to obtain a worst-case o((4/9) (n-m)2((m + p)p/(p-1)!))-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. © 2014 hongfa wang and wei ding.