树状网络上最大时延最小化的p-Proxy选址问题

Minimum the Longest Delay p-proxy Problem on Tree Graphs

该文研究在树状网络上如何放置给定的P个代理服务器(Proxy),使得整个网络的最大时延最小化的问题,即最优放置代理服务器问题。该文利用文献6动态规划的方法在O(pn2)多项式时间内给出该问题的最优解。

We study the problem of optimal placement of proxies.Given P proxies,find the optimal placement of the proxies on tree graphs,such that the longest delay for any client to access the web server is minimized.Optimal results are obtained in O(pn2) polynomial time by using a dynamic programming method.