کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436670 690022 2014 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the approximability of the link building problem
ترجمه فارسی عنوان
در تقریبی بودن مشکل ساختن پیوند
کلمات کلیدی
ساخت لینک رتبه صفحه، بهینه سازی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We consider the LINK BUILDING problem, which involves maximizing the PageRank value of a given target vertex in a directed graph by adding k   new links that point to the target (backlinks). We present a theorem describing how the topology of the graph affects the choice of potential new backlinks. Based on this theorem we show that no fully polynomial-time approximation scheme (FPTAS) exists for LINK BUILDING unless P=NPP=NP and we also show that LINK BUILDING is W[1]W[1]-hard.Furthermore, we show that this problem is in the class APX by presenting the polynomial time algorithm r-Greedy, which selects new backlinks in a greedy fashion and results in a new PageRank value for the target vertex that is within a constant factor from the best possible. We also consider the naive algorithm π-Naive, where we choose backlinks from vertices with high PageRank values compared to the out-degree and show that this algorithm performs much worse on certain graphs compared to our constant factor approximation. Finally, we provide a lower bound for the approximation ratio of our r-Greedy algorithm.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 518, 23 January 2014, Pages 96–116
نویسندگان
, ,