  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 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.
