کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428361 | 686642 | 2007 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Primal-dual approximation algorithms for the Prize-Collecting Steiner Tree Problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The primal-dual scheme has been used to provide approximation algorithms for many problems. Goemans and Williamson gave a (2−1/(n−1))-approximation for the Prize-Collecting Steiner Tree Problem that runs in O(n3logn) time—it applies the primal-dual scheme once for each of the n vertices of the graph. We present a primal-dual algorithm that runs in O(n2logn), as it applies this scheme only once, and achieves the slightly better ratio of (2−2/n). We also show a tight example for the analysis of the algorithm and discuss briefly a couple of other algorithms described in the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 103, Issue 5, 31 August 2007, Pages 195-202
Journal: Information Processing Letters - Volume 103, Issue 5, 31 August 2007, Pages 195-202