کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420292 | 683916 | 2006 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of maximum matroid–greedoid intersection and weighted greedoid maximization
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown NP-hard by expressing the satisfiability of boolean formulas in 3-conjunctive normal form as such an intersection. The corresponding approximation problems are shown NP-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown W[P]-hard. The results are in contrast with the maximum matroid–matroid intersection which is solvable in polynomial time by an old result of Edmonds. We also prove that it is NP-hard to approximate the weighted greedoid maximization within 2nO(1)2nO(1) where n is the size of the domain of the greedoid.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 4, 15 March 2006, Pages 684–691
Journal: Discrete Applied Mathematics - Volume 154, Issue 4, 15 March 2006, Pages 684–691
نویسندگان
Taneli Mielikäinen, Esko Ukkonen,