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
Approximation Scheme
Polynomial Time Algorithm
Fully Polynomial Time Approximation Scheme
Subscribe
Academic
Publications
A ConstantFactor Approximation Algorithm for the Link Building Problem
A ConstantFactor Approximation Algorithm for the Link Building Problem,10.1007/9783642174612_7,Martin Olsen,Anastasios Viglas,Ilia Zvedeniouk
Edit
A ConstantFactor Approximation Algorithm for the Link Building Problem
BibTex

RIS

RefWorks
Download
Martin Olsen
,
Anastasios Viglas
,
Ilia Zvedeniouk
In this work we consider the problem of maximizing the PageRank of a given target node in a graph by adding k new links. We consider the case that the new links must point to the given target node (backlinks). Previous work [7] shows that this problem has no fully polynomial time approximation schemes unless P = NP. We present a
polynomial time algorithm
yielding a PageRank value within a constant factor from the optimal. We also consider the naive algorithm where we choose backlinks from nodes with high PageRank values compared to the outdegree and show that the naive algorithm performs much worse on certain graphs compared to the constant factor approximation scheme.
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 8796, 2010
DOI:
10.1007/9783642174612_7
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
adsabs.harvard.edu
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
References
(9)
THE EFFECT OF NEW LINKS ON GOOGLE PAGERANK
(
Citations: 12
)
Konstantin Avrachenkov INRIA
,
Nelly Litvak
Published in 2007.
Inside PageRank
(
Citations: 151
)
Monica Bianchini
,
Marco Gori
,
Franco Scarselli
Journal:
ACM Transactions on Internet Technology  TOIT
, vol. 5, no. 1, pp. 92128, 2005
The anatomy of a largescale hypertextual Web search engine
(
Citations: 4676
)
Sergey Brin
,
Lawrence Page
Journal:
Computer Networks and Isdn Systems  CN
, vol. 30, no. 17, pp. 107117, 1998
Maximizing PageRank via outlinks
(
Citations: 7
)
Cristobald de Kerchove
,
Laure Ninove
,
Paul van Dooren
Journal:
Linear Algebra and Its Applications  LINEAR ALGEBRA APPL
, vol. 429, no. 5, pp. 12541276, 2008
Deeper Inside {PageRank
(
Citations: 243
)
Amy N. Langville
,
Carl D. Meyer
Journal:
Internet Mathematics
, vol. 1, no. 2003, pp. 335380, 2004