Weighted cache location problem with identical servers

DOI10.1155/2014/586146MaRDI QIDQ2336558zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hongfa Wang, Wei Ding

Publication date 19 November 2019

Published in Journal of Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.1155/2014/586146

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Analysis of algorithms (68W40) Programming involving graphs or networks (90C35)

Review text

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.

Recommendations

• The multiple server location problem
• The multiple server center location problem
• scientific article; zbMATH DE number 1500546
• The weighted 2-server problem
• The gravity multiple server location problem
• Computational Science and Its Applications – ICCSA 2004
• scientific article; zbMATH DE number 3896624
• scientific article; zbMATH DE number 1409906

Cites work

• A fast parallel algorithm for finding a most reliable source on a general ring-tree graph with unreliable edges
• A note on two problems in connexion with graphs
• An O(pn^ 2) algorithm for the p-median and related problems on tree graphs
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Graph theory with applications
• scientific article; zbMATH DE number 919106 (Why is no real title available?)
• Monge strikes again: Optimal placement of web proxies in the internet
• On the 2-MRS problem in a tree with unreliable edges
• Placement of Web-Server Proxies with Consideration of Read and Update Operations on the Internet
• The web proxy location problem in general tree of rings networks

This page was built for publication: Weighted cache location problem with identical servers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2336558)