Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Approximate Algorithm
Assignment Problem
Polynomial Time
Search Trees
Subscribe
Academic
Publications
Constant factor approximations for the hotlink assignment problem
Constant factor approximations for the hotlink assignment problem,10.1145/1921659.1921662,ACM Transactions on Algorithms,Tobias Jacobs
Edit
Constant factor approximations for the hotlink assignment problem
BibTex

RIS

RefWorks
Download
Tobias Jacobs
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 khotlink
assignment problem
denotes the task of adding at most k outgoing hotlinks to each page of a treelike 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 polynomialtime 2approximation for the 1hotlink 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.
Journal:
ACM Transactions on Algorithms  TALG
, vol. 7, no. 2, pp. 119, 2011
DOI:
10.1145/1921659.1921662
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
doi.acm.org
)
More »
References
(16)
Dynamic Hotlinks
(
Citations: 5
)
Karim Douïeb
,
Stefan Langerman
Conference:
Workshop on Algorithms and Data Structures  WADS
, pp. 182194, 2005
NearEntropy Hotlink Assignments
(
Citations: 7
)
Karim Douïeb
,
Stefan Langerman
Journal:
Algorithmica
, vol. 58, no. 2, pp. 292303, 2006
Multiple Hotlink Assignment
(
Citations: 14
)
Sven Fuhrmann
,
Sven Oliver Krumke
,
Hanschristoph Wirth
Conference:
Workshop on GraphTheoretic Concepts in Computer Science  WG
, pp. 189200, 2001
An Experimental Study of Recent Hotlink Assignment Algorithms
(
Citations: 4
)
Tobias Jacobs
Journal:
ACM Journal of Experimental Algorithms  JEA
, vol. 15, pp. 142151, 2008
On the Complexity of Optimal Hotlink Assignment
(
Citations: 2
)
Tobias Jacobs
Conference:
European Symposium on Algorithms  ESA
, pp. 540552, 2008