CAJ | 학술논문

该文考虑网络数据更新,需要控制代理服务器与客户的距离时,网络中的代理服务器的放置问题.找到代理服务器的最优数量和放置位置,使网络中数据访问的总花费(包括数据读取和更新)最小.利用二叉树结构和动态规划方法,得到了一个时间复杂度O(n2)的多项式时间算法,其中n为网络结点数.
해문고필망락수거경신,수요공제대리복무기여객호적거리시,망락중적대리복무기적방치문제.조도대리복무기적최우수량화방치위치,사망락중수거방문적총화비(포괄수거독취화경신)최소.이용이차수결구화동태규화방법,득도료일개시간복잡도O(n2)적다항식시간산법,기중n위망락결점수.
The paper discusses the Web proxy location problem with consideration of both read and update operations to the data on the Internet when controlling the distance between the Web proxies and the server and finds the optimal number of proxies and their placement,such that the overall access cost is minimized.An algorithm with time complexity O(n~2) is gotten which uses binary tree and the dynamic programming,where n is the number of nodes in the net.