Approximation Algorithm for Hotlink Assignments in Web Directories
Approximation Algorithm for Hotlink Assignments in Web Directories
复制标题
Web 目录中热链接分配的近似算法
DOI：
10.1007/978-3-540-45078-8_24
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Rachel Matichin;D. Peleg
热链接分配涉及将快捷链接添加到基于链接节点(例如网络)的信息结构。结构中的每个节点与表示该节点被用户访问的频率的权重相关联。要访问节点，用户必须遵循从根指向该节点的路径。向该结构引入额外的边(热链接)可以降低其访问成本，该成本被认为是从根到达节点所需的预期步骤数。防盗链分配的问题是找到一组防盗链，使接入成本得到最大改善。本文介绍了该问题的一个近似比为2的近似算法。
Hotlink assignment concerns the addition of shortcut links to information structures based on linked nodes such as the web. Each node in the structure is associated with a weight representing the frequency that node is accessed by users. To access a node, the user must follow the path leading to it from the root. Introducing additional edges (hotlinks) to the structure may reduce its access cost, taken to be the expected number of steps needed to reach a node from the root. Thehotlink assignmentproblem is to find a set of hotlinks achieving the greatest improvement in the access cost. This paper introduces an approximation algorithm for this problem with approximation ratio 2.