کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420740 | 683976 | 2006 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for the bi-criteria weighted MAX-CUT problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider a generalization of the classical MAX-CUT problem where two objective functions are simultaneously considered. We derive some theorems on the existence and the non-existence of feasible cuts that are at the same time near optimal for both criteria. Furthermore, two approximation algorithms with performance guarantee are presented. The first one is deterministic while the second one is randomized. A generalization of these results is given for the bi-criteria MAX-k-CUT problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 12, 15 July 2006, Pages 1685–1692
Journal: Discrete Applied Mathematics - Volume 154, Issue 12, 15 July 2006, Pages 1685–1692
نویسندگان
Eric Angel, Evripidis Bampis, Laurent Gourvès,