Weighted cache location problem with identical servers (Q2336558)

Summary: This paper extends the well-known \(p\)-CLP with one server to \(p\)-CLP with \(m \geq 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(p h^2 + n)\)-time parallel exact algorithm for \(p\)-CLP on a tree and then present a parallel exact algorithm with at most \(O((4 / 9) p^2 n^2)\) 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.