Constant Approximation Hotlink Assignment Algorithm

Karim Douieb

Consider a directed rooted tree T representing a collection of web pages connected via a set of links. All pages are reachable from a source home page, corresponding to the root of T. Each web page carries a weight representative of the frequency with which it is visited. By adding hotlinks, shortcuts from a node to one of its descendents, we are interested in minimizing the expected number of steps needed to visit pages from the homepage. In this talk, I will present a 3-approximation algorithm for assigning one hotlink per node of a tree T in O(n log n) time.