Weighted Cache Location Problem with Identical Servers
Joint Authors
Source
Journal of Applied Mathematics
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-11, 11 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-08-24
Country of Publication
Egypt
No. of Pages
11
Main Subjects
Abstract EN
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 ( 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.
American Psychological Association (APA)
Wang, Hongfa& Ding, Wei. 2014. Weighted Cache Location Problem with Identical Servers. Journal of Applied Mathematics،Vol. 2014, no. 2014, pp.1-11.
https://search.emarefa.net/detail/BIM-1039742
Modern Language Association (MLA)
Wang, Hongfa& Ding, Wei. Weighted Cache Location Problem with Identical Servers. Journal of Applied Mathematics No. 2014 (2014), pp.1-11.
https://search.emarefa.net/detail/BIM-1039742
American Medical Association (AMA)
Wang, Hongfa& Ding, Wei. Weighted Cache Location Problem with Identical Servers. Journal of Applied Mathematics. 2014. Vol. 2014, no. 2014, pp.1-11.
https://search.emarefa.net/detail/BIM-1039742
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1039742