Optimal approximability of bookmark assignments

Consider a rooted directed acyclic graph G=(V,E)G=(V,E) with root rr, representing a collection VV of web pages connected via a set EE of hyperlinks. Each node vv is associated with the probability that a user wants to access the node vv. The access cost is defined as the expected number of steps required to reach a node from the root rr. A bookmark is an additional shortcut from rr to a node of GG, 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≠NPP≠NP: we present a polynomial time approximation algorithm with factor (1−1/e)(1−1/e), and show that there exists no polynomial time approximation algorithm with a better constant factor than (1−1/e)(1−1/e) unless P=NPP=NP.