Constant factor approximations for the hotlink assignment problem

摘要

The concept of hotlink assignment aims at reducing the navigation effort for the users of a Web directory or similar structure by inserting a limited number of additional hyperlinks called hotlinks. The k-hotlink assignment problem denotes the task of adding at most k outgoing hotlinks to each page of a tree-like site, minimizing the path length, that is, the expected number of "clicks" necessary for the user to reach her destination page. Another common formulation of this problem is to maximize the gain, that is, the path length reduction achieved by the assignment. In this work we analyze the natural greedy strategy, proving that it reaches the optimal gain up to the constant factor of 2. Considering the gain, we also prove the existence of a PTAS. Finally, we give a polynomial-time 2-approximation for the 1-hotlink assignment problem, which constitutes the first constant factor approximation in terms of the path length. The algorithms' performance analyses are made possible by a set of three new basic operations for the transformation of hotlink assignments.