کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649472 1342457 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on submodular set cover on matroids
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A note on submodular set cover on matroids
چکیده انگلیسی

We consider a problem related to the submodular set cover on polymatroids, when the ground set is the family of independent sets of a matroid. The achievement here is getting a strongly polynomial running time with respect to the ground set of the matroid even though the family of independent sets has exponential size. We also address the optimization problem of the maximization of submodular set functions on the independent sets of a matroid.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 18, 28 September 2009, Pages 5739–5744
نویسندگان
, ,