TY - JOUR
T1 - Monge strikes again : optimal placement of web proxies in the internet
AU - Woeginger, G.J.
PY - 2000
Y1 - 2000
N2 - In a recent paper (Proceedings of IFIP’98), Li et al. study the problem of placing m web proxies in the internet under a given traffic pattern. They consider the special case of a linear net topology with n nodes. Their goal is to minimize the overall latency of accessing the target web server subject to the network resources and traffic pattern. They show how this problem can be solved in O(n2m) time. In this short note, we observe that one of the underlying cost functions in this problem carries a Monge structure. By exploiting this structure and by applying some well-known results from the literature, we get a faster algorithm with time complexity O(nm).
AB - In a recent paper (Proceedings of IFIP’98), Li et al. study the problem of placing m web proxies in the internet under a given traffic pattern. They consider the special case of a linear net topology with n nodes. Their goal is to minimize the overall latency of accessing the target web server subject to the network resources and traffic pattern. They show how this problem can be solved in O(n2m) time. In this short note, we observe that one of the underlying cost functions in this problem carries a Monge structure. By exploiting this structure and by applying some well-known results from the literature, we get a faster algorithm with time complexity O(nm).
U2 - 10.1016/S0167-6377(00)00041-9
DO - 10.1016/S0167-6377(00)00041-9
M3 - Article
VL - 27
SP - 93
EP - 96
JO - Operations Research Letters
JF - Operations Research Letters
SN - 0167-6377
IS - 3
ER -