کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421119 | 684142 | 2015 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximate tradeoffs on weighted labeled matroids
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider problems where a solution is evaluated with a couple. Each coordinate of this couple represents the utility of an agent. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for both agents. Then a natural aim is to find a tradeoff. We investigate tradeoff solutions with worst case guarantees for the agents. The focus is on discrete problems having a matroid structure and the utility of an agent is modeled with a function which is either additive or weighted labeled. We provide polynomial-time deterministic algorithms which achieve several guarantees and we prove that some guarantees are not possible to reach.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 154–166
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 154–166
نویسندگان
Laurent Gourvès, Jérôme Monnot, Lydia Tlilane,