Laber and Molinaro study the hotlink assignment problem, in which direct links between pages are added to an existing Web site to minimize the time users spend searching for information. A Web site is represented by a graph G, where G is a rooted direct tree. In the hotlink assignment version of the problem, the expected user path length is minimized by summing over the new expected distance between the root and each node in the hotlinked tree multiplied by the popularity of each node. The k-assignment problem allows for up to k hotlinks to be added to each node in the tree. In the gain hotlink assignment version of the problem, the gain is maximized. Gain here is the difference between the expected path length in the given tree and the expected path length in a hotlinked tree.

The authors first show the existence of fully polynomial time approximation algorithms for the hotlink assignment and the gain hotlink assignment problems, where at most one hotlink may be assigned to each page. These are the best possible results one may achieve under the assumption that $P\; \ne \; NP$. The authors also provide a 16-approximation algorithm for the k hotlink assignment problem. This is the first algorithm with constant approximation for this problem.

While the problem studied has practical applications, the paper itself is only accessible to experts in approximation algorithms. Thus, I recommend it for this audience.