Approximate hotlink assignment

Evangelos Kranakis, Danny Krizanc, Sunil Shende

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

Consider a directed rooted tree T = (V,E) of maximal degree d representing a collection V of web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each leaf 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 the leaf pages from the home page. We give an O(N 2) time algorithm for assigning hotlinks so that the expected number of steps to reach the leaves from the root of the tree is at most H(p)/ log(d+1)-(d/(d+1)) log d + d+1/d, where H(p) is the entropy of the probability (frequency) distribution p =< p1,p2, pN > on the N leaves of the given tree, i.e., pi is the weight on the ith leaf. The best known lower bound for this problem is H(p)/ log(d+1). Thus our algorithm approximates the optimal hotlink assignment to within a constant for any fixed d.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
Pages756-767
Number of pages12
DOIs
StatePublished - Dec 1 2001
Event12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, New Zealand
Duration: Dec 19 2001Dec 21 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2223 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Symposium on Algorithms and Computation, ISAAC 2001
CountryNew Zealand
CityChristchurch
Period12/19/0112/21/01

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximate hotlink assignment'. Together they form a unique fingerprint.

  • Cite this

    Kranakis, E., Krizanc, D., & Shende, S. (2001). Approximate hotlink assignment. In Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings (pp. 756-767). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2223 LNCS). https://doi.org/10.1007/3-540-45678-3_64