کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142727 | 957161 | 2010 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved approximation algorithm for requirement cut
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This note presents improved approximation guarantees for the requirement cut problem: given an nn-vertex edge-weighted graph G=(V,E)G=(V,E), and gg groups of vertices X1,…,Xg⊆VX1,…,Xg⊆V with each group XiXi having a requirement riri between 0 and |Xi||Xi|, the goal is to find a minimum cost set of edges whose removal separates each group XiXi into at least riri disconnected components. We give a tight Θ(logg)Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk⋅logg)O(logk⋅logg) approximation ratio for general graphs, where k=|∪i=1gXi|≤n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 38, Issue 4, July 2010, Pages 322–325
Journal: Operations Research Letters - Volume 38, Issue 4, July 2010, Pages 322–325
نویسندگان
Anupam Gupta, Viswanath Nagarajan, R. Ravi,