...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Optimal approximability of bookmark assignments
【24h】

Optimal approximability of bookmark assignments

机译：书签分配的最佳近似性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：考虑以根r为根的有向有向无环图G =（V，E），它表示通过一组超链接E连接的网页集合V。每个节点v与用户想要访问节点v的概率相关。访问成本定义为从根r到达节点所需的预期步骤数。书签是从r到G节点的附加快捷方式，可以减少访问成本。书签分配问题是找到一组可以最大程度地提高访问成本的书签。针对该问题，本文显示了在假设P≠NP的​​情况下（in）逼近度的严格界限：我们提出了一个因数为（1-1 / e）的多项式时间逼近算法，并且表明不存在多项式时间逼近算法除非P = NP，否则常数因子比（1-1 / e）好。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号