| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-08-23 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Optimal approximability of bookmark assignments |
|
言語 |
en |
| その他のタイトル |
|
|
その他のタイトル |
Optimal Approximability of Bookmark Assignments |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
宮野, 英次
Murata, Toshihide
Ono, Hirotaka
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
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. |
|
言語 |
en |
| 書誌情報 |
en : Discrete Applied Mathematics
巻 161,
号 16-17,
p. 2361-2366,
発行日 2013-06-15
|
| 出版社 |
|
|
出版者 |
Elsevier |
| DOI |
|
|
関連タイプ |
isIdenticalTo |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1016/j.dam.2013.05.018 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0166-218X |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1872-6771 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2013 Elsevier B.V. All rights reserved. |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Bookmark assignment |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Approximation algorithm |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Inapproximability |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
10347771.pdf (148 KB)
