Approximation algorithm for hotlink assignment in the greedy model
Approximation algorithm for hotlink assignment in the greedy model
复制标题
贪心模型中热链接分配的近似算法
DOI：
10.1016/j.tcs.2007.03.045
复制
发表时间：
2004
影响因子：
1.1
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Rachel Matichin;D. Peleg
通过增加热链接，可以加强网络等基于链接的信息结构。假设信息结构中的每个节点与表示用户对节点的访问频率的权重相关联。为了访问一个特定的节点，用户必须沿着一条从根节点指向它的路径。通过向树添加新的热链接，可以减少系统的访问成本，即从根到达叶子所需的预期步骤数，假设用户可以决定在每个步骤中遵循哪些热链接。hotlink分配问题涉及到找到一组hotlink（每个节点发出的hotlink最多为K=O（1）），使预期成本的收益最大化。本文在两个用户模型中解决了这个问题，即，在[P. Bose，J. Czyzowicz，L. Gasieniec，E. Kranakis，D. Krizanc，A. Pelc，M.V. Martin，Strategies for hotlink assignments，in：Proc. 11th Symp.算法和计算，2000年，pp。23-34; E. Kranakis，D. Krizanc，S. Shende，Approximating hotlink assignments，in：Proc. 12th Symp.算法和计算，2001年，pp。756-767; P. Bose，D. Krizanc，S.杨文龙，非对称通信协议的研究，北京大学出版社，2002年。33-39; R. Matichin，D. Peleg，Web目录中hotlink分配的近似算法，在：Proc。算法和数据结构研讨会，2003年，第100页。271-280]和最近在[O. Gerstel，S.库滕河Matichin，D. Peleg，网络目录的Hotlink增强算法，在：Proc.14th Symp。算法和计算，2003年，pp。68-77]，并给出了有根有向树上热链接分配问题的多项式时间2-近似算法。
Link-based information structures such as the web can be enhanced through the addition of hotlinks. Assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. In order to access a particular node, the user must follow a path leading to it from the root. By adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. The hotlink assignment problem involves finding a set of hotlinks (with at most K=O(1) hotlinks emanating from every node) maximizing the gain in the expected cost. The paper addresses this problem in two user models, namely, the traditional clairvoyant user model employed in [P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc, M.V. Martin, Strategies for hotlink assignments, in: Proc. 11th Symp. on Algorithms and Computation, 2000, pp. 23–34; E. Kranakis, D. Krizanc, S. Shende, Approximating hotlink assignments, in: Proc. 12th Symp. on Algorithms and Computation, 2001, pp. 756–767; P. Bose, D. Krizanc, S. Langerman, P. Morin, Asymmetrical communication protocols via hotlink assignments, in: Proc. 9th Colloq. on Structural Information and Communication Complexity, 2002, pp. 33–39; R. Matichin, D. Peleg, Approximation algorithm for hotlink assignments in web directories, in: Proc. Workshop on Algorithms and Data Structures, 2003, pp. 271–280] and the more realistic greedy user model recently introduced in [O. Gerstel, S. Kutten, R. Matichin, D. Peleg, Hotlink enhancement algorithms for web directories, in: Proc. 14th Symp. on Algorithms and Computation, 2003, pp. 68–77], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on rooted directed trees.