Weighted Cache Location Problem with Identical Servers

Hongfa Wang and Wei Ding

Journal of Applied Mathematics, 2014, vol. 2014, issue 1

Abstract: 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.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2014/586146

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2014:y:2014:i:1:n:586146

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().