Optimal approximability of bookmark assignments
Optimal approximability of bookmark assignments
复制标题
书签分配的最佳近似性
DOI：
10.1016/j.dam.2013.05.018
复制
发表时间：
2013
影响因子：
1.1
通讯作者：
Hirotaka Ono
中科院分区：
文献类型：
--
作者：
Yuichi Asahiro;Eiji Miyano;Toshihide Murata;Hirotaka Ono
考虑一个有根有向无环图 G=(V, E)，根为 r，表示通过一组 E 超链接连接的网页集合 V。每个节点 v 与用户想要访问节点 v 的概率相关联。访问成本定义为从根 r 到达节点所需的预期步骤数。书签是从r到G的节点的附加快捷方式，可以降低访问成本。书签分配问题是找到一组对访问成本实现最大改进的书签。对于这个问题，本文展示了假设 P≠ NP 下（in）逼近性的紧界：我们提出了一种因子为 (1− 1/e) 的多项式时间逼近算法，并表明除非 P= NP，否则不存在具有比 (1− 1/e) 更好的常数因子的多项式时间逼近算法。
Consider a rooted directed acyclic graph G=(V, E) with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper shows the tight bound on the (in) approximability under the assumption P≠ NP: we present a polynomial time approximation algorithm with factor (1− 1/e), and show that there exists no polynomial time approximation algorithm with a better constant factor than (1− 1/e) unless P= NP.